链表：环形检测与入口节点

环形链表：Floyd 判圈算法

判断链表是否有环，可以用快慢指针（Floyd's Tortoise and Hare）：

• 慢指针 每次走 1 步，快指针 每次走 2 步
• 若有环，快指针必然追上慢指针（在环内相遇）
• 若无环，快指针先到达 null

判断是否有环（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;
}

找环的入口节点（LeetCode 142）

数学推导：

设链表头到环入口距离为 a，环入口到相遇点距离为 b，环的剩余长度为 c（环长 = b + c）。

• 慢指针走了：a + b
• 快指针走了：a + b + k(b+c)，其中 k 为圈数

由于快指针速度是慢指针的 2 倍：2(a+b) = a + b + k(b+c) → a = k(b+c) - b

当 k=1 时：a = c

结论：从相遇点出发 + 从链表头出发，以相同速度（每次走 1 步）同时走，会在环入口相遇！

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // Phase 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;
    // Phase 2: 找环入口
    slow = head;  // slow 回到 head
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;  // fast 从相遇点以 1 步继续走
    }
    return slow;  // 相遇即为环入口
}

两链表相交（LeetCode 160）

同样利用"走完自己走对方"的技巧：

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;  // 走完 A 就走 B
        b = (b == null) ? headA : b.next;  // 走完 B 就走 A
    }
    return a;  // 相交则为交点，无交叉则同时到 null
}

原理：设 A 独占段长 a，B 独占段长 b，公共段长 c。

• pA 走：a + c + b，pB 走：b + c + a，路程相同，若有交叉则在交叉点相遇。

回文链表（LeetCode 234）

找中点 + 反转后半 + 对比：

boolean isPalindrome(ListNode head) {
    // 1. 快慢指针找中点
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. 反转后半部分
    ListNode prev = null, cur = slow;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    // 3. 比较
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

快慢指针综合运用

删除链表倒数第 N 个节点（LeetCode 19）

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;  // fast 先走 n+1 步
    while (fast != null) { slow = slow.next; fast = fast.next; }
    slow.next = slow.next.next;  // 删除节点
    return dummy.next;
}