0234. Palindrome Linked List¶
题目信息¶
- 题号:
0234
- 难度:
Easy
- 主题:
单链表、回文、双指针
- 原题:
- 重点:
按节点值序列判断、正读与反读完全相同、奇偶长度、常数空间进阶
题目重述¶
给定一个非空单链表的头节点 head,按照从头到尾访问得到节点值序列。若该序列从左向右和从右向左读取完全相同,返回 true;否则返回 false。比较的是节点值及其顺序,不是节点地址是否对称。
链表节点数位于 [1, 10^5],每个节点值位于 [0, 9]。单节点链表一定是回文;奇数长度链表的中间节点不需要与其他位置配对。题目只要求返回判断结果,进阶要求为 O(n) 时间和 O(1) 额外空间。
自建示例¶
偶数长度回文:
输入:head = [4, 1, 1, 4]
输出:true
解释:从头到尾和从尾到头得到的值序列都为 [4, 1, 1, 4]。
相同值数量不足以构成回文:
输入:head = [2, 5, 2, 5]
输出:false
解释:反向序列为 [5, 2, 5, 2],与原顺序不同。
找中点、反转后半段¶
用快慢指针定位后半段起点:fast 每次走两步,slow 每次走一步。
循环结束时,偶数长度链表的 slow 已指向后半段首节点;奇数长度时 fast 仍非空,
slow 位于中间节点,再向前移动一步跳过中间值。中间节点不需要比较。
把后半段原地反转后,从头节点和反转后的后半段首节点同步比较。后半段长度不大于前半段, 只要所有对应值相同就是回文。比较结束后再把后半段反转一次,恢复原链表方向,避免判断函数留下结构副作用。
正确性说明¶
快慢指针的步速差保证 slow 的位置如上;跳过奇数长度的中点不会遗漏任何需要配对的值。
反转后,后半段从头到尾的顺序正好对应原链表从尾到中点的顺序,因此逐项比较等价于比较整个序列与其逆序。
若存在不等值位置,序列不是回文;若全部匹配,所有对称位置相等。恢复操作只反转同一段,不改变比较结论。
C++ 实现¶
class Solution {
ListNode* reverseList(ListNode* head) {
ListNode* previous = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = previous;
previous = head;
head = next;
}
return previous;
}
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != nullptr) slow = slow->next;
ListNode* reversed = reverseList(slow);
ListNode* first = head;
ListNode* second = reversed;
bool palindrome = true;
while (second != nullptr) {
if (first->val != second->val) {
palindrome = false;
break;
}
first = first->next;
second = second->next;
}
reverseList(reversed);
return palindrome;
}
};
代码分析¶
快慢指针、反转和比较各自只遍历链表常数次,时间复杂度为 O(n);反转使用固定指针,
额外空间为 O(1)。reversed 保存反转段的入口,比较提前失败时仍会执行恢复,
所以无论返回真或假,原链表结构都恢复为调用前状态。