链表双指针（快慢指针 · 中间节点 · 环形链表）

快慢指针核心思想

• 快指针每次走 2 步，慢指针每次走 1 步
• 若有环：快慢指针必定在环内相遇
• 若无环：快指针先到达 null

链表的中间节点（LeetCode 876）

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // 偶数长度时返回第二个中间节点
}

环形链表 I（LeetCode 141）

判断是否有环：

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

环形链表 II（LeetCode 142）

找到环的入口节点（Floyd 判圈算法）：

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // 1. 找到相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;  // 无环

    // 2. 一个指针从头，一个从相遇点，同速走，再次相遇即是入口
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

数学证明：

• 设 head 到入口距离 = a，入口到相遇点 = b，相遇点到入口 = c
• 慢走 a+b，快走 a+b+c+b = a+2b+c
• 快 = 2×慢 → a+2b+c = 2(a+b) → c = a
• 所以从 head 和相遇点同速走 a 步，恰好在入口汇合

相交链表（LeetCode 160）

找两个链表的交叉起始节点：

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;  // 走到末尾就切换到另一链表头
        b = (b == null) ? headA : b.next;
    }
    return a;
}

原理：两指针各走 lenA + lenB 步后必然同在交叉点（或同为 null）。

排序链表（LeetCode 148）

O(n log n) 时间 O(1) 空间 → 归并排序（自底向上）：

ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 找中点，断开
    ListNode mid = getMid(head);
    ListNode right = mid.next;
    mid.next = null;
    // 递归排序
    ListNode l = sortList(head);
    ListNode r = sortList(right);
    return mergeTwoLists(l, r);
}

private ListNode getMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // 偶数时返回前半部分最后一个
}

重排链表（LeetCode 143）

L0→L1→…→Ln → L0→Ln→L1→Ln-1→L2→Ln-2→…

三步：

1. 找中间节点（快慢指针）
2. 反转后半部分
3. 交替合并

void reorderList(ListNode head) {
    // 1. 找中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    // 2. 反转后半部分
    ListNode second = reverseList(slow.next);
    slow.next = null;
    // 3. 交替合并
    ListNode first = head;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}