题目要求

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

Follow up:
Can you solve it without using extra space?

如何找到环的第一个节点？

根据题目意图，我们可以构建如下模型：

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是v,2v。

由slow和fast第一次在点Z相遇，我们可以得出以下等式：

　　　　　　　　2(a+b)=(a+2b+c)

　　　　　　　=> a=c

由此可见，a和c的长度一样。因此我们可以将slow重新定位到头结点，然后fast与slow以相同的速度前进，相遇的节点Y则是环的开始节点。

代码实现：

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        ListNode* slow=head;

        ListNode* fast=head;

        while(true){

            if(fast==nullptr||fast->next==nullptr){

                return nullptr;

            }

            slow=slow->next;

            fast=fast->next->next;

            if(fast==slow){

                break;

            }

        }

        slow=head;

        while(slow!=fast){

            slow=slow->next;

            fast=fast->next;

        }

        return slow;

    }

};

巴特西

Linked List Cycle II--寻找单链表中环的起始点

题目要求

最新文章

热门文章