如何判断一个字符串是不是回文串 时间复杂度o 空间复杂度o
最新回答
节操嘎嘣脆
2026-07-27 12:11:08
由于空间复杂度的要求，需要就地操作链表，不能开辟多余的空间来进行处理，因此引入快慢指针来进行操作。
快慢指针： slow 和 fast，每次slow指针前进一步，fast指针前进两步，当遇到指针为空时说明遍历链表完成，此时也就可以找到链表的中心位置。
注意，由于链表的长度可能是奇数也可能是偶数，因此应该做一个判断。
找到链表的中心后，把链表的后半部分进行就地逆转，就地逆转是采用头插法即可。
后半部分逆转完成后，将链表的前半部分和后半部分一次比较，即可判断是否是回文。
实现代码如下：
链表类定义：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
链表就地反转：
public static ListNode reverseList(ListNode head){
ListNode ptr = head, ptr2 = head;
ListNode fast = head.next;
while(fast!=null){
//头插法
ptr = fast.next;
fast.next = head;
head = fast;
fast = ptr;
}
//反转完成后将原头指针的next设置为null
ptr2.next = null;
return head;
}
判断链表是否是回文：
1 public static boolean isPalindrome(ListNode head){
2 if(head==null || head.next==null){
3 return true;
4 }
5 //建立快慢指针，寻找链表中心
6 ListNode slow = head;
7 ListNode fast = head;
8 while(fast!=null && fast.next!=null){
9 slow = slow.next;
10 fast = fast.next.next;
11 }
12
13 if(fast == null){
14 //偶数个元素(进行链表反转)
15 ListNode ptr = slow, ptr2 = slow;
16 ListNode fast1 = slow.next;
17 while(fast1!=null){
18 ptr = fast1.next;
19 fast1.next = slow;
20 slow = fast1;
21 fast1 = ptr;
22 }
23 ptr2.next = null;
24 }else{
25 //奇数个元素(进行链表反转)
26 ListNode ptr = slow.next,ptr2 = slow.next;
27 ListNode fast1 = slow.next.next;
28 while(fast1 != null){
29 ptr = fast1.next;
30 fast1.next = slow.next;
31 slow.next = fast1;
32 fast1 = ptr;
33 }
34 ptr2.next = null;
35 slow = slow.next;
36 }
37
38 while(slow!=null){
39 if(head.val!=slow.val)
40 return false;
41 slow = slow.next;
42 head = head.next;
43 }
44 return true;
45 }
46
47 }
热门标签
