HHot 100C++ 图解

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 i0 2 i1 2 i2 1 i3
链表结构(来自本仓库测试数据)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/07_linked_list.cpp32 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q234_palindrome_list12 行
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);

↑↓ 选择↵ 打开/ 随时唤起