环链表寻找交点

目录

1.题目描述和出处

2.分析

3.代码

---

1.题目描述和出处

LCR 022. 环形链表 II - 力扣（LeetCode）

描述很简单，寻找交点，找到则返回交点，找不到返回空。

---

2.分析

如图：（b表示环的长度）

本题要使用快慢指针的思想。

定义一个快指针f，一个慢指针s。快指针每次从头走两步，慢指针从头走一步。若存在环，则快指针一定能追上慢指针。

那么，现在让快慢指针第一次出发：

设f走了2L的距离，s走了L的距离(快指针每次从头走两步，慢指针从头走一步)。

当f和s相遇时：表示f套圈追上了s，假设套了n圈则有 2L - L = nb -> L = nb;

若从起点出发到达交点的距离可以用a+nb来表示，而s刚好走了nb的距离，也就是说再让s走a的距离就到达了交点，但是我们并不知道a的值。

我们第二次需要让快指针重新出发：

此时，我们让快指针回到起点并且每次直走一步和慢指针保持一致。

那么当他们第二次相遇的时候一定就是交点位置。

原因：当f走了a长度的路程时，这时b走的距离为nb+a。

我们有结论：a+nb表示达到交点，而n取0就是a。

也就是他们同时到达了交点，此时返回任意一个就是最终结果。

---

3.代码

ListNode *detectCycle(ListNode *head) {
        //快慢指针
        ListNode* f=head;
        ListNode* s=head;
        while(true)
        {
            //当快指针可以找到末尾时
            //表示没有环的存在
            if(f == nullptr || f->next == nullptr)
            return nullptr;
            //快指针走俩步 慢指针走一步
            f=f->next->next;
            s=s->next;
            if(f == s)
            break;
        }
        //从头开始重新找一遍，相遇的位置即为交点
        f=head;
        while(true)
        {
            if(f == s)
            break;
            f=f->next;
            s=s->next;
        }
        return f;
    }