首页 > 代码库 > 【LeetCode】Linked List Cycle II

【LeetCode】Linked List Cycle II

2024-07-03 13:55:12   221人阅读

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

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

 

首先不考虑Follow up的要求，那就比较简单了。

创建一个map，存放已经出现过的指针，直到next为空或者next指向的指针出现过。

class Solution {
public:
    map<ListNode *, bool> m;
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* p = head;

        while(p != NULL)
        {
            if(m.find(p) == m.end())
            {
                m.insert(map<ListNode *, bool>::value_type(p, true));
                p = p->next;
            }
            else
                return p;
        }
        return NULL;
    }
};

 

考虑不创建额外存储空间的情况。

有个不靠谱想法是，寻找一个与链表中的val都不同的val_unique，将所有遍历过的节点都置为val_unique，

直到next为空或者next指向的节点为val_unique。

虽然在平台上使用INT_MIN可以AC，但是INT_MIN是否就是unique，这是无法判断的。

上不靠谱代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* p = head;

        while(p != NULL)
        {
            if(p->val == INT_MIN)
                return p;
            else
            {
                p->val = INT_MIN;
                p = p->next;
            }
        }
        return NULL;
    }
};

 

最后参考了Discussion中提到的龟兔赛跑算法，经过理解实现，将思路与代码整理如下：

兔(fast)每次前进两步(若两步中出现NULL，则返回NULL).

龟(slow)每次前进一步(若出现NULL，则返回NULL).

当出现环路，则总有某时刻，兔会赶上龟（相遇），证明如下：

1、若兔子套圈之前在龟后方两步，则兔2龟1之后，兔子在龟后方一步，进入(2)

2、若兔子套圈之前在龟后方一步，则兔2龟1之后，兔子追上龟（相遇）

其他情况均可化归到以上两步。

假设从head到环入口entry步数为x，环路长度为y，相遇时离entry的距离为m

则兔：x+ay+m，龟：x+by+m  (a > b)

x+ay+m = 2(x+by+m)

整理得x+m = (a-b)y

以上式子的含义是，相遇时的位置(m)再前进x步，正好是y的整倍数即整圈。

现在的问题是怎样计数x。

利用head到entry的长度为x，只要龟从head每次前进一步，兔从相遇位置每次前进一步，

再次相遇的时候即环的入口。

class Solution {
public:

    ListNode *detectCycle(ListNode *head) 
    {
        if(head == NULL)
            return NULL;

        ListNode* fast = head;
        ListNode* slow = head;

        do
        {
            if(fast->next != NULL && slow->next != NULL)
            {
                fast = fast->next;
                if(fast->next != NULL)
                    fast = fast->next;
                else
                    return NULL;
                slow = slow->next;
            }
            else
                return NULL;
        }while(fast != slow);

        slow = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

这里的循环有个小技巧，用do...while而不是while，来保证第一次判断结束条件时兔子已经比龟多前进了一步。

 


联系
我们