Ripple's Blog

快慢双指针

3 min read

核心思想

两个指针同向移动，慢指针每次走 1 步，快指针每次走 2 步。利用速度差来判断链表结构或找到特殊位置，无需额外空间。

适用场景

判断链表是否为环

slow走1步，fast走2步，fast 追上 slow 说明有环，fast 到达 null 说明无环。

为什么一定会相遇？进入环后，每轮 fast 比 slow 多走 1 步，相对距离每轮减 1，必然归零。

相关题目：Leetcode 141.环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode* sl = head, *fa = head->next;
        while (sl != fa) {
            if (fa == nullptr || fa->next == nullptr) return false;
            sl = sl->next;
            fa = fa->next->next;
        }
        return true;
    }
};

判断环形链表的入口

使用Floyd 判圈算法，当我们用快慢指针使它们相遇后，再将链表的头节点和相遇点同时向前移动，当它们相遇（注意这里说的它们是链表头节点和快慢指针的相遇点，不是第一次快慢指针）时，那个点就是环形链表的入口。

数学证明（记住结论即可）： 设链表头到入口距离 = a，入口到相遇点 = b，环长 = c。
相遇时：2(a+b) = a+b+c → a = c−b
即：从 head 到入口的距离 = 从相遇点继续走到入口的距离。
所以把 slow 重置到 head，fast 留在相遇点，同速走，再次相遇即入口。

相关题目：Leetcode 142

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* sl = head, *fa = head;
        while (true) {
            if (fa == nullptr || fa->next == nullptr) {
                return nullptr;
            }
            sl = sl->next;
            fa = fa->next->next;
            if (sl == fa) {
                break;
            }
        }
        sl = head;
        while (sl != fa) {
            sl = sl->next;
            fa = fa->next;
        }
 
        return sl;
    }
};

寻找链表的中间点

同样是快慢指针，慢指针走一步，快指针走两步。 当快指针走完链表时，慢指针正好停在了链表的中间位置。

相关题目：Leetcode 876

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* sl = head, *fa = head;
        while (fa && fa->next) {
            sl = sl->next;
            fa = fa->next->next;
        }
        return sl;
    }
};

注意对于偶数长度的链表，中间点有两个，比如长度为6的链表第3，4都是中间点。上面的代码选择的是后面那个，如果要返回前面那个改为fa = head->next即可，但要注意空指针的情况。

Graph View