题目描述

题目链接：142. Linked List Cycle II

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

例子

见官网题目例子。

Follow Up

Can you solve it using O(1) (i.e. constant) memory?

Note

Constraints

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

解题思路

这道题是 [Leetcode]141. Linked List Cycle(C++) 的延伸，上一道题中通过分别移动快慢指针，通过最后是否相遇可以判断链表中是否有环。这道题则要求我们找到环开始的位置，如果不限制使用空间的话，用哈希表存储我们经过的节点，第一次遇到相同的节点时就表明该位置是环开始的位置。

这道题做法是：同样通过两个节点 a b 快慢移动，当他们相遇时，它们走过的长度差为环的长度（快指针刚好比慢指针跑快了一圈），同时快指针走过的长度是慢指针走过的长度的两倍，因此可以得出，慢指针走过的长度刚好是换的长度，这里拆分一下有：len(head->环起点) + len(环起点->慢指针位置) = len(环) 即: len(head->环起点) = len(环) - len(环起点->慢指针位置), 此时把其中一个节点放回 head 然后让两个节点一步一步迭代，当从 head 开始的指针走到环起点时，另一个指针刚好走了 len(环) - len(环起点->慢指针位置)，不难看出此时这个指针刚好也指向环起点，因此判断条件是当两个指针重新相遇时，它们指向的节点就是环起点。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head){

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

        int diff_fast_slow = 0;

        while (fast && slow) {
            if (!fast->next || !fast->next->next) return nullptr;

            fast = fast->next->next;
            slow = slow->next;

            if (fast == slow) break;
        }

        slow = head;

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

        return fast;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 142.LinkedListCycleIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions