数据结构的探究学习 ——链表的回文结构

Han.miracle

发布于 2025-12-22 14:10:53

400

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

链表的回文结构

回文（Palindrome）是指从前往后读和从后往前读完全相同的字符串或数列。要求：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

第一步：特殊情况处理

if (A == null || A.next == null) return true;

空链表或者只有一个结点，肯定是回文。

第二步：快慢指针找中点

ListNode slow = A, fast = A;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
//slow 每次走一步，fast 每次走两步。
//当 fast 走到链表末尾时，slow 正好落在 中点。

👉 用来判断链表奇偶长度：

如果 fast == null → 链表长度为偶数，slow 停在右半段的起点。

如果 fast != null → 链表长度为奇数，slow 停在正中间。

第三步：确定后半段起点

ListNode second = (fast != null) ? slow.next : slow;
//三目运算符进行判断

如果是奇数长度（fast != null），需要跳过中点，后半段从 slow.next 开始。例如：1 → 2 → 3 → 2 → 1，slow=3，应从 3 后面的 2 开始。

2）链表长度是奇数

例子：1 → 2 → 3 → 2 → 1

快慢指针停下时：

fast != null

slow 指向中间的 3

所以：second = slow.next = 2（跳过中点，从 3 后面开始）

反转后半段 2 → 1 → 得到 1 → 2

此时 prev 指向 1，也就是 原链表的最后一个结点。

👉 结论：奇数情况下，prev 也最终指向 原链表尾结点，不是中间点。

如果是偶数长度（fast == null），后半段从 slow 开始。例如：1 → 2 → 2 → 1，slow 停在第二个 2，就是后半段的起点。两种情况分析

1）链表长度是偶数

例子：1 → 2 → 2 → 1

快慢指针停下时：

fast == null

slow 指向右边第一个 2

所以：second = slow = 2（右半段起点）

反转后半段 2 → 1 → 得到 1 → 2

此时 prev 指向 1，也就是 原链表的最后一个结点。

👉 结论：偶数情况下，prev 最终指向 原链表尾结点。

第四步：反转后半段

ListNode prev = null, cur = second;
while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

这是链表反转的标准三步。

反转完成后，prev 指向后半段反转后的头。

👉 举例：

原链表：1 → 2 → 3 → 2 → 1

后半段：2 → 1

反转后：1 → 2

第五步：前后两段比较

ListNode p1 = A, p2 = prev;
while (p2 != null) {
    if (p1.val != p2.val) return false;
    p1 = p1.next;
    p2 = p2.next;
}

用两个指针从链表头和反转后的后半段同时出发。
逐个结点比较值。
只要有不相等，说明不是回文。
如果后半段全部匹配完（p2=null），说明是回文。

第六部：回复链表

       cur = prev; prev = null;
       while (cur != null) {
          ListNode next = cur.next;
          cur.next = prev;
          prev = cur;
            cur = next;
         }
         // 如果是奇数长度：slow.next = prev；偶数长度：slow = prev；
         if (fast != null) slow.next = prev; else {
             // 偶数长度时，slow 原本就是第二段起点，需要把整段接回去
         }

① cur = prev; prev = null;

此时 prev 指向反转过的后半段链表的头。

我们要把后半段再反转回来，因此让 cur = prev，准备重新走一遍反转。

prev = null 是初始化，标准反转链表套路。

再次反转后半段

while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

这就是反转链表的标准三步。

反转完成后，prev 就变成了恢复好的后半段的头。

举例：

比较前：2 → 1

反转过来比较：1 → 2

恢复时再反转：2 → 1 ✅，和最初一样。

if (fast != null) slow.next = prev; else {
    // 偶数长度时，slow 原本就是第二段起点，需要把整段接回去
}

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // 1) 快慢指针找中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2) 奇数长度跳过中点；偶数长度从 slow 开始
        ListNode second = (fast != null) ? slow.next : slow;

        // 3) 反转后半段
        ListNode prev = null, cur = second;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // prev 为“后半段反转后”的头

        // 4) 前后两段逐个比较（只比后半段长度）
        ListNode p1 = head, p2 = prev;
        boolean ok = true;
        while (p2 != null) {
            if (p1.val != p2.val) { ok = false; break; }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 5) （可选）恢复后半段，保持链表结构不变
        // cur = prev; prev = null;
        // while (cur != null) {
        //     ListNode next = cur.next;
        //     cur.next = prev;
        //     prev = cur;
        //     cur = next;
        // }
        // // 如果是奇数长度：slow.next = prev；偶数长度：slow = prev；
        // if (fast != null) slow.next = prev; else {
        //     // 偶数长度时，slow 原本就是第二段起点，需要把整段接回去
        // }
          //return ok;
    }

// 5) （可选）恢复后半段，保持链表结构不变
cur = prev; 
prev = null;
// 先把后半段再反转回去
while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
// 此时 prev 指向恢复好的“后半段头”

if (fast != null) {
    // 奇数长度：slow 在中点，后半段起点是 slow.next
    slow.next = prev;
} else {
    // 偶数长度：slow 本身就是后半段起点
    // 我们要找到前半段的尾巴，让它重新指向恢复好的后半段
    ListNode p = head;
    while (p.next != null && p.next != slow) {
        p = p.next;
    }
    p.next = prev;
}
      
}

🔎 思路解释

cur = prev; prev = null; while (…) 这一段：