[LeetCode] 142. Linked List Cycle II 單鏈表中的環(huán)之二

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

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

這個(gè)求單鏈表中的環(huán)的起始點(diǎn)是之前那個(gè)判斷單鏈表中是否有環(huán)的延伸，可參之前那道 Linked List Cycle。這里還是要設(shè)快慢指針，不過這次要記錄兩個(gè)指針相遇的位置，當(dāng)兩個(gè)指針相遇了后，讓其中一個(gè)指針從鏈表頭開始，一步兩步，一步一步似爪牙，似魔鬼的步伐。。。哈哈，打住打住。。。此時(shí)再相遇的位置就是鏈表中環(huán)的起始位置，為啥是這樣呢，這里直接貼上熱心網(wǎng)友「飛鳥想飛」的解釋哈，因?yàn)榭熘羔樏看巫?，慢指針每次走1，快指針走的距離是慢指針的兩倍。而快指針又比慢指針多走了一圈。所以 head 到環(huán)的起點(diǎn)+環(huán)的起點(diǎn)到他們相遇的點(diǎn)的距離 與 環(huán)一圈的距離相等?，F(xiàn)在重新開始，head 運(yùn)行到環(huán)起點(diǎn) 和 相遇點(diǎn)到環(huán)起點(diǎn) 的距離也是相等的，相當(dāng)于他們同時(shí)減掉了 環(huán)的起點(diǎn)到他們相遇的點(diǎn)的距離。代碼如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        if (!fast || !fast->next) return NULL;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/142

類似題目：

Linked List Cycle

Find the Duplicate Number

參考資料：

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

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(142.單鏈表中的環(huán)之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)單鏈表中的環(huán)之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論