秋招知识库

主题

题目链接 · 灵神原题解（署名来源）

前言 ​

回想一下，怎么判断一个字符串是不是回文串？我们可以从最左最右开始，比较第一个字母和最后一个字母是不是一样的，一样的话，就继续比较第二个字母和倒数第二个字母，依此类推。这个过程会从左到右遍历字符串，以及从右到左遍历字符串。

对于链表，如何从右到左遍历呢？

方法一：递归 ​

递归的「归」的过程，就是从右到左遍历链表的过程。

下面这个递归函数可以从右到左打印链表的节点值：

python
def f(node):
    if node is None:
        return
    f(node.next)
    print(node.val)  # 注：如果把这行代码移到 f(node.next) 的上面，就是从左到右打印

f(head)
cpp
// C++ 版待补充

在「归」的过程中，用另一个指针 left 从左到右遍历链表，就可以比较对称位置的值是否相等了。

注：递归做法效率比较低，更快的做法见方法二。

python
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        left = head

        def is_pal(right: Optional[ListNode]) -> bool:
            # 「递」，先把 right 移到链表末尾
            if right.next and not is_pal(right.next):
                return False
            # 「归」的过程就是在从右到左遍历链表
            nonlocal left
            if left.val != right.val:
                return False
            left = left.next  # left 往右走
            return True  # 归，right 会往左走

        return is_pal(head)
cpp
// C++ 版待补充
cpp
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* left = head;

        // lambda 递归函数
        auto is_pal = [&](this auto&& is_pal, ListNode* right) -> bool {
            // 「递」，先把 right 移到链表末尾
            if (right->next && !is_pal(right->next)) {
                return false;
            }
            // 「归」的过程就是在从右到左遍历链表
            if (left->val != right->val) {
                return false;
            }
            left = left->next; // left 往右走
            return true; // 归，right 会往左走
        };

        return is_pal(head);
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 是链表的长度（节点个数）。
  • 空间复杂度：O(n)。递归需要 O(n) 的栈空间。

方法二：迭代 ​

前置题目：

首先，找链表的中间节点：

  • 如果链表有奇数个节点，找正中间的节点。lc-midlist1.jpg
  • 如果链表有偶数个节点，找正中间右边的节点。lc-midlist2.jpg

然后，把中间节点到链表末尾反转。如上图，反转后得到链表 6→5→4，其头节点记作 head2。这样我们就能从 head2 开始，依次访问原链表的最后一个节点、倒数第二个节点、倒数第三个节点……

最后，同时遍历 head 和 head2 这两个链表，每次循环判断 head.val 是否等于 head2.val，若不相等，则返回 false。循环直到 head2 链表遍历结束。如果循环中没有返回 false，说明链表是回文的，返回 true。

⚠注意：第一张图中的 2→3，在反转链表后，并不会断开。第一张图反转链表后，我们得到了两条链表，一条是 1→2→3，另一条是 5→4→3。

⚠注意：第二张图中的 3→4，在反转链表后，并不会断开。第二张图反转链表后，我们得到了两条链表，一条是 1→2→3→4，另一条是 6→5→4。这意味着下面代码在写循环的时候，循环条件要判断 head2 是否为空而不是 head 是否为空。如果判断 head 是否为空，会错误地多循环一次，导致访问 head2.val 出现空指针异常。

答疑 ​

问：为什么不能反转整个链表？

答：注意我们还要从 head 开始，从左到右遍历链表。如果反转整个链表，链表前半段的结构就被破坏了，无法从 head 开始访问后续节点。

下面的代码修改了输入的链表。复原输入的写法可以参考【Python3 写法二】。

python
class Solution:
    # 876. 链表的中间结点
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    # 206. 反转链表
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:  # 不是回文链表
                return False
            head = head.next
            head2 = head2.next
        return True
cpp
// C++ 版待补充
python
class Solution:
    # 876. 链表的中间结点
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    # 206. 反转链表
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        mid = self.middleNode(head)
        head2 = h2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:  # 不是回文链表
                self.reverseList(h2)  # 复原
                return False
            head = head.next
            head2 = head2.next
        self.reverseList(h2)  # 复原
        return True
cpp
// C++ 版待补充
cpp
class Solution {
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, *cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

public:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid);
        while (head2) {
            if (head->val != head2->val) { // 不是回文链表
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

复杂度分析 ​

  • 时间复杂度：O(n)，其中 n 是链表的长度（节点个数）。
  • 空间复杂度：O(1)。

分类题单 ​

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

本文整理自灵茶山艾府（endlesscheng）的公开内容，仅供个人学习使用
本站为个人秋招复习知识库 · 仅供个人学习使用

本站仅供个人学习使用，请勿外传

秋招知识库