Linked List Cycle II

Description:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.

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

Link:

https://leetcode.com/problems/linked-list-cycle-ii/description/

解题方法:

参考了博客

image.png

用快慢指针可以得知链表是否有环。
如上图所示,假如链表起点为X,环入口为Y,快慢指针第一次在Z点相遇。X->Y = a,Y->Z = b,Z->Y = c。
则有: 2(a + b) = a + n(b + c) + b
即:a = n(b + c) - b
也就是说,如果用两个指针分别从X和Z往下走,一定会在Y点相遇,也就是所求的环的起点。

Time Complexity:

O(N)

完整代码:

class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        do
        {
            if(fast == NULL || fast->next == NULL)
                return NULL;
            slow = slow->next;
            fast = fast->next->next;
        }
        while(fast != slow);
        slow = head;
        while(slow != fast)
        {
            if(slow == NULL || fast == NULL)
                return NULL;
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容