LeetCode——142 设计链表2

题目

代码

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        ListNode *fast = head, *slow = head;

        while(fast && fast->next){

            fast = fast->next->next;

            slow = slow->next;

            if(fast == slow){

                break;

            }

        }

        if(!fast || !fast->next){

            return NULL;

        }

        slow = head;

        while(slow!=fast){

            slow = slow->next;

            fast = fast->next;

        }

        return slow;

    }

};

思路

简单说下思路，现在已经知道的条件：

快指针移动速度为慢指针两倍；
快指针要比慢指针多移动一圈；

可得：

假设\(L\)为链表入口到环入口的距离，\(x\)为环入口到相遇点的距离，\(C\)为环的周长，可得：

\(2 \times (L + x) - (L + x) = C\)，即\(L + x = C\)，可得：\(x = C - L\)，即相遇点到环入口的距离与链表入口到环入口的距离相等，所以可以通过让慢指针回到链表入口，然后快慢指针同时一步一步地前进，最后相遇的地方就是环的入口。

巴特西

LeetCode——142 设计链表2

题目

代码

思路

最新文章

热门文章