234. 回文链表

考点

  • 快慢指针/双指针
  • 链表的反转

题解

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
class Solution {
private:
bool judgeFunc(ListNode* head, ListNode* midNode) {
for (ListNode *left = head, *right = midNode->next; right != nullptr; left = left->next, right = right->next) {
if (left->val != right->val) return false;
}
return true;
}

ListNode* reverseList(ListNode* dummyHead) {
ListNode *tail = dummyHead->next;
while (tail->next != nullptr) {
ListNode *node = tail->next;
tail->next = node->next;
node->next = dummyHead->next;
dummyHead->next = node;
}
return dummyHead;
}

ListNode* findMid(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

public:
bool isPalindrome(ListNode* head) {
if (head->next == nullptr) return true;
return (judgeFunc(head, reverseList(findMid(head))));
}
};

思路

验证回文串,最直接的方法就是双指针,左指针从头向尾遍历,右指针从尾向头遍历,只要两个指针指向的值不一样就肯定不是回文串

  1. 子问题:两个指针反向遍历,比较两个指针指向的值

  2. 递归语句顺序:递归方向分为一去一回,去方向到达临界点后返回;这里只能在回方向操作,因为右指针需要从尾向头遍历

    左指针怎么办呢?额外单独设置一个成员变量即可,待右指针开始从尾向头遍历时再做比较

  3. 返回值:不需要返回值

  4. 临界点:右指针为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
bool ans;
ListNode *left;
void recursiveFunc(ListNode *right) {
if (right == nullptr) return;
recursiveFunc(right->next);
if(left->val != right->val) ans = false;
left = left->next;
}

public:
bool isPalindrome(ListNode* head) {
left = head;
ans = true;
recursiveFunc(head);
return ans;
}
};

但题目要求只能以常数空间复杂度运行,故而不能使用递归;用迭代分为以下几个步骤

  1. 找到链表中心点,分为左、右两个子链表
  2. 右子链表反转
  3. 即可对左、右两个子链表进行同向比较了

这里有一个可有可无的Trick

如果是奇数个链表节点,比如{1, 2, 3, 4, 5},找到的链表中心点是3

如果是偶数个链表节点,比如{1, 2, 3, 4},则找到的链表中心点应为2

这样中心点就可以作为右子链表的dummyHead,便于反转