234. 回文链表
一句话套路快慢找中 + 反转后半 + 逐一比对
题目描述
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1] 输出:true
示例 2:
输入:head = [1,2] 输出:false
提示:
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路
时间
O(n)空间
O(1)思路
快慢指针找中点 -> 反转后半段 -> 双向比对 -> 还原链表。
O(1) 空间的唯一正解;数组化 O(n) space 是备用答案。
偶数长度时 slow 落在后半段起点,比较时用 q 走完为止,不必管长度。
加分项
还原链表(不破坏输入),面试官会认为你「有工程意识」。
图解
链表结构(来自本仓库测试数据)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0234 {
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode *slow = head, *fast = head;
while (fast && fast->next) { // 定位后半段起点
slow = slow->next;
fast = fast->next->next;
}
auto reverseFrom = [](ListNode* p) {
ListNode* prev = nullptr;
while (p) {
ListNode* n = p->next;
p->next = prev;
prev = p;
p = n;
}
return prev;
};
ListNode* second = reverseFrom(slow);
bool ok = true;
for (ListNode *p = head, *q = second; q; p = p->next, q = q->next)
if (p->val != q->val) {
ok = false;
break;
}
reverseFrom(second); // 还原,恢复入参原貌
return ok;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0234::Solution s;
ListNode* a = buildList({1, 2, 2, 1});
CHECK_TRUE(s.isPalindrome(a));
CHECK_EQ(listToVec(a), vector<int>{1, 2, 2, 1}); // 验证已被还原
freeList(a);
ListNode* b = buildList({1, 2});
CHECK_FALSE(s.isPalindrome(b));
freeList(b);
ListNode* c = buildList({1, 2, 1}); // 奇数长度
CHECK_TRUE(s.isPalindrome(c));
CHECK_EQ(listToVec(c), vector<int>{1, 2, 1});
freeList(c);