本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
请判断一个链表是否为回文链表。
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
示例 1:
示例 2:
链接：
https://leetcode-cn.com/problems/palindrome-linked-list
题目分析
判断回文我们可以使用双指针的方法，从两边同时遍历判断是否相等，但是这道题的数据结构是单链表。第一个方法是将其拷贝到数组中再使用双指针，第二个方法是使用递归，反向获得链表的值，并与正向的相比较。但是这两种方法的空间复杂度都是 $O(n)$。如何达到 $O(1)$ 的空间复杂度呢？我们应该要使用迭代的方法。
我们可以先使用快慢指针找到链表的中点，并用 Leetcode 206.反转链表 中的迭代法将后半部分翻转。翻转后两条链表应该是相同的（除了奇数结点的中间结点），这样我们就可以迭代判断是否符合回文特性了。然后我们再将后半部分翻转一遍（相当于复原）接回原链表。这样做是为了不破坏原链表的结构。
注意代码中快慢指针寻找到的中点是前半部分的最后一个结点，并且如果结点数是奇数，最中间的结点会包含在前半部分中。这样做的好处是后半部分的开头可以直接通过前半部分结尾获得，并且复原后也是接到前半部分的结尾中。而由于奇数中间结点包含在前半部分中，我们判断回文的退出条件是后半部分遍历完成，这样这个结点无需进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
ListNode* findFirstHalfEnd(ListNode* head){
ListNode *fast = head;
ListNode *slow = head;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* head) {
if(head == nullptr) return nullptr;
ListNode *pre = head;
ListNode *p = head->next;
head->next = nullptr;
while(p != nullptr){
ListNode *next = p->next;
p->next = pre;
pre = p;
p = next;
}
return pre;
}
public:
bool isPalindrome(ListNode* head) {
ListNode *firstHalfEnd = findFirstHalfEnd(head);
ListNode *secondHalfBegin = reverseList(firstHalfEnd->next);
bool result = true;
ListNode *p = head;
ListNode *q = secondHalfBegin;
while(q != nullptr){
if(p->val != q->val){
result = false;
break;
}
p = p->next;
q = q->next;
}
firstHalfEnd->next = reverseList(secondHalfBegin);
return result;
}
};
|
时间复杂度：$O(n)$，其中 $n$ 是链表的长度。我们对链表进行的寻找中点操作、反转操作、判断回文操作都是 $O(n)$ 的。
空间复杂度：$O(1)$。我们所有的操作都是通过指针迭代进行的，需要的空间是常数级的。