Fast & Slow Pointers

快慢指針是雙指針的特例：兩個指針同方向出發，但速度不同（典型是慢的走一步、快的走兩步）。在無法用索引隨機存取的結構（如鏈結串列）上，靠兩者的相對位置就能取得「中點」「環」「倒數第 k 個」等資訊，全程只掃一兩遍、O(1) 額外空間。

找中點

快指針每次走兩步、慢指針走一步；快指針到底時，慢指針剛好在中點。

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }
    return slow   // 偶數長度時回傳偏右的中點
}

偵測環（Floyd 龜兔演算法）

若有環，快指針終會「套圈」追上慢指針；若無環，快指針會先抵達 null。

fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) return true   // 相遇即有環
    }
    return false
}

找環的入口

相遇後，把其中一個指針移回 head，兩指針都改成每次一步，再次相遇處就是環的入口。

fun detectCycle(head: ListNode?): ListNode? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) {            // 第一次相遇
            var p = head
            while (p !== slow) {        // 同速前進，再會於入口
                p = p?.next
                slow = slow?.next
            }
            return p
        }
    }
    return null
}

找倒數第 k 個節點

讓快指針先走 k 步，再讓兩指針一起前進；快指針到底時，慢指針正好在倒數第 k 個。這就是「移除倒數第 k 個節點」的一趟解法。

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(0).apply { next = head }
    var fast: ListNode? = dummy
    var slow: ListNode? = dummy
    repeat(n + 1) { fast = fast?.next }   // 快指針先走 n+1 步
    while (fast != null) {
        fast = fast?.next
        slow = slow?.next
    }
    slow?.next = slow?.next?.next         // 跳過倒數第 n 個
    return dummy.next
}

跨倉庫導讀

• 對應理論章節：線性資料結構
• 另見本書 Two Pointers 的相向／同向指針技法。