快慢指针

一、基本原理

快慢指针也叫双指针（快慢型），多用于链表、数组场景。 定义两个指针：

• 慢指针：每次走 1 步
• 快指针：每次走 2 步

利用两者步速差，实现位置判断、环检测、中点查找、倒数节点查找等功能。

二、常见应用场景

1. 判断链表是否有环

思路

有环链表中，快指针会进入环内循环，最终一定追上慢指针；无环则快指针先走到链表末尾。

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

2. 寻找链表中环的入口节点

思路

快慢指针相遇后，将其中一个指针移到链表头，两个指针同速前进，再次相遇处即为环入口。

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

3. 查找链表中间节点

思路

快指针走到末尾时，慢指针恰好指向中点。

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

4. 查找链表倒数第 n 个节点

思路

先让快指针先走 n 步，之后快慢指针同速前进，快指针到尾时，慢指针就是倒数第 n 个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode slow = dummy;
    ListNode fast = dummy;
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

三、复杂度分析

• 时间复杂度：$O(n)$，仅遍历链表常数次
• 空间复杂度：$O(1)$，仅使用两个指针，额外空间极小

四、面试相关问题

1. 问：快慢指针的原理是什么？答： 设置两个步长不同的指针，慢指针每次走1步，快指针每次走2步，依靠步速差完成链表环检测、找中点、找倒数节点等操作，空间复杂度为 O(1)。

2. 问：如何判断链表有环？答： 使用快慢指针遍历，若快慢指针相遇说明存在环；若快指针走到链表末尾，则无环。

3. 问：怎么找到链表环的入口？答： 先通过快慢指针找到相遇点，再将一个指针置于链表头部，两指针以相同速度移动，再次相遇的位置就是环的入口。

4. 问：快慢指针和普通遍历相比优势？答： 不需要额外数组/哈希表存储节点，原地操作，空间复杂度更低，效率更高。