回文链表 图解题解

判断回文，链表比数组难在哪

回文的定义是正着读和反着读一样。数组版本很好办：左右两个位置向中间对撞比较即可。链表的麻烦在于单向——每个节点只认识自己的 next，没法从尾巴往回走。最省事的做法是把所有值复制进数组再对撞，时间 O(n) 但空间也是 O(n)；题目的进阶要求是 O(n) 时间、O(1) 空间，等于禁止复制，逼你在链表本身的指针上做文章。

为什么反转后半段就能原地比较

回文有一个等价说法：把整条链的后半段方向翻转，它应该和前半段逐个相等。顺着这个观察，解法只需三步：先找到中点，再把从中点开始的后半段就地反转——此时原来的尾节点变成了可以正向遍历的头——最后让两个指针分别从原链头和这个新头出发同步比较。单链表不能倒着走的缺陷，被「把后半段翻个方向」绕开了，全程只改指针、不建新节点。

快慢指针为什么恰好停在中点

找中点用快慢指针：slow 每次走一步，fast 每次走两步，fast 到达链尾时 slow 恰好走完一半路程，停在中间。这一步就是 LeetCode 876 链表的中间结点，可以单独拿出来练。更妙的是奇偶长度被统一处理：奇数长度时 slow 停在正中那个节点，它不属于任何一半，天然不参与比较；偶数长度时前后正好各占一半——两种情况共用同一套代码，不需要分支特判。

反转和比较这两步，正确性各在哪里

反转来自 LeetCode 206：遍历后半段，把每个节点的 next 掉头指向前驱。关键是掉头之前必须先用临时变量存住原来的 next，否则指针一改链就断了，后继再也找不回来。

比较阶段以后半段指针走到 null 为终止条件：反转后的后半段长度不超过前半段，它走完就意味着所有成对的位置都比完了，继续多走没有意义；途中任何一对值不相等，立刻返回 false 即可。

复杂度、副作用与面试加分点

三个阶段分别扫链表的一半到一遍，总时间 O(n)；只用了常数个指针变量，空间 O(1)，正是进阶要的答案。要留意这个解法有副作用：比较结束后链表的后半段仍处于反转状态。严谨的做法是返回之前把后半段再反转一次复原；面试时主动提到这一点，能体现出「函数不应悄悄改坏输入」的工程意识。

Python

def isPalindrome(head):
    # ① 快慢找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # ② 从 slow 起反转后半
    prev = None
    cur = slow
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    # ③ 首尾对撞比较
    p1, p2 = head, prev
    while p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next
    return True

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        // ① 快慢找中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // ② 从 slow 起反转后半
        ListNode prev = null, cur = slow;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        // ③ 首尾对撞比较
        ListNode p1 = head, p2 = prev;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}

JavaScript

function isPalindrome(head) {
  // ① 快慢找中点
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // ② 从 slow 起反转后半
  let prev = null, cur = slow;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  // ③ 首尾对撞比较
  let p1 = head, p2 = prev;
  while (p2) {
    if (p1.val !== p2.val) return false;
    p1 = p1.next;
    p2 = p2.next;
  }
  return true;
}

C++

bool isPalindrome(ListNode* head) {
    // ① 快慢找中点
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // ② 从 slow 起反转后半
    ListNode *prev = nullptr, *cur = slow;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    // ③ 首尾对撞比较
    ListNode *p1 = head, *p2 = prev;
    while (p2) {
        if (p1->val != p2->val) return false;
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}