【LeetCode 热题 100】234. 回文链表——快慢指针+反转链表

Problem: 234. 回文链表
题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

整体思路

这段代码旨在解决一个经典的链表问题：回文链表 (Palindrome Linked List)。问题要求判断一个单链表是否是回文结构，即从前向后读和从后向前读的序列是否相同。例如 1 -> 2 -> 3 -> 2 -> 1 是回文链表。

该算法采用了一种非常高效且空间优化的 “快慢指针 + 反转后半部分 + 比较” 的三步走策略。它避免了使用额外数组存储所有节点，从而实现了 O(1) 的空间复杂度。

1. 第一步：使用快慢指针找到链表的中点

   • 算法初始化两个指针 slow 和 fast，都指向链表的头节点 head。
   • 通过一个 while 循环，让 fast 指针每次移动两步，slow 指针每次移动一步。
   • 这个循环的终止条件是 fast 到达或越过链表的末尾。当循环结束时：
     • 如果链表长度为奇数，slow 指针会恰好停在链表的正中间节点。
     • 如果链表长度为偶数，slow 指针会停在后半部分链表的第一个节点。
   • 无论哪种情况，slow 指针都为我们准确地划分出了链表的后半部分。

2. 第二步：反转链表的后半部分

   • 从 slow 指针指向的节点开始，就是链表的后半部分。
   • 算法调用一个辅助函数 reverseList(slow)，将这后半部分的链表进行原地反转。
   • 反转后，会得到一个新的头节点 head2，它指向反转后的后半部分的链表。

3. 第三步：比较前半部分和反转后的后半部分

   • 现在，我们有了两个“子链表”需要比较：
     • 原始链表的前半部分，从 head 开始。
     • 反转后的后半部分，从 head2 开始。
   • 通过一个 while 循环，同时遍历这两个子链表（循环条件是 head2 != null，因为后半部分可能比前半部分短一个节点，在奇数长度情况下）。
   • 在循环中，比较两个指针指向节点的值 head.val 和 head2.val。
     • 如果任何一对节点的值不相等，说明链表不是回文结构，立即返回 false。
     • 如果值相等，则将两个指针都向前移动一步。
   • 如果循环正常结束（即所有对应的节点值都相等），说明链表是回文的，返回 true。

注意：这个算法会修改原始链表的结构（后半部分被反转）。如果题目要求不能修改原链表，则需要在比较完成后再将后半部分反转回来恢复原状。

完整代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 判断一个单链表是否是回文链表。
     * @param head 链表的头节点
     * @return 如果是回文链表则返回 true，否则返回 false
     */
    public boolean isPalindrome(ListNode head) {
        // 步骤 1: 使用快慢指针找到链表的中点或后半部分的起点
        ListNode slow = head;
        ListNode fast = head;
        // fast 每次走两步，slow 每次走一步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 循环结束后，slow 指向了后半部分的头节点
        
        // 步骤 2: 反转链表的后半部分
        // head2 是反转后链表的头节点
        ListNode head2 = reverseList(slow);
        
        // 步骤 3: 比较前半部分和反转后的后半部分
        // head 指向原始链表的头，head2 指向反转后半部分的头
        while (head2 != null) {
            // 如果对应节点的值不相等，则不是回文链表
            if (head.val != head2.val) {
                return false;
            }
            // 移动两个指针，继续比较下一对节点
            head = head.next;
            head2 = head2.next;
        }
        
        // 如果循环正常结束，说明所有对应节点都相等，是回文链表
        return true;
    }

    /**
     * 辅助函数：原地反转一个单链表（迭代法）。
     * @param head 要反转的链表的头节点
     * @return 反转后新链表的头节点
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    } 
}

时空复杂度

时间复杂度：O(N)

算法主要包含三个步骤，我们分别分析其时间复杂度：

1. 查找中点：快慢指针遍历链表，slow 指针走了 N/2 步。时间复杂度为 O(N)。
2. 反转后半部分：reverseList 函数被调用在链表的后半部分，其长度约为 N/2。反转一个长度为 k 的链表需要 O(k) 的时间。因此，这部分的时间复杂度是 O(N)。
3. 比较两部分：最后的 while 循环遍历了链表的后半部分，长度约为 N/2。时间复杂度为 O(N)。

综合分析：
算法的总时间复杂度是 O(N) + O(N) + O(N) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：该算法没有使用任何与输入规模 N 成比例的额外数据结构（如数组或哈希表）。
2. 辅助变量：
   • 在 isPalindrome 方法中，只使用了 slow, fast, head2 等几个指针变量。
   • 在 reverseList 方法中，也只使用了 pre, cur, nxt 等几个指针变量。
   • 这些变量的数量是固定的，与链表长度无关。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是一个空间效率最优的原地算法。