题目描述
回文链表
请判断一个链表是否为回文链表。
示例 1 :
示例 2 :
进阶 :
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法一
最直观的想法是将链表中的所有值都读到数组中，然后判断是否为回文。时间复杂度为O(n)，空间复杂度O(n)。
解法二（快慢指针）
慢指针指向链表的开始位置，快指针先走到链表结尾处，比较值是否相等；然后慢指针走一步，快指针走n - 1步（走到结尾再回到开头），再比较值，直到快慢指针相遇（即慢指针走到链表的一半处）。时间复杂度为O(n2)，空间复杂度为O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr)
return true;
ListNode *slow = head, *fast = head;
int size = 1;
while (fast->next) {
fast = fast->next;
size++;
}
for (int i = 0; i < size / 2; i++) {
if (slow->val != fast->val)
return false;
slow = slow->next;
for (int j = 0; j < size - 1; j++) {
fast = fast->next;
if (!fast)
fast = head;
}
}
return true;
}
};
|
解法三（翻转链表）
先走到链表中点，再将之后的链表翻转，用双指针分别从链表的开头和结尾开始向中点移动并比较。例如 1->2->2->1 翻转成 1->2<-2<-1；1->2->3->2->1 翻转成 1->2->3<-2<-1。时间复杂度为O(n)，空间复杂度为O(1)。
用快慢指针的方式可快速找到链表的中点（慢指针走一步，快指针走两步）。
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
| class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr)
return true;
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
while (fast) {
ListNode *tmp = fast;
fast = fast->next;
tmp->next = slow;
slow = tmp;
}
fast = head;
while (fast && slow) {
if (fast->val != slow->val) {
return false;
}
fast = fast->next;
slow = slow->next;
}
return true;
}
};
|