[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?

這個求單鏈表中的環(huán)的起始點是之前那個判斷單鏈表中是否有環(huán)的延伸，可參之前那道 Linked List Cycle。這里還是要設快慢指針，不過這次要記錄兩個指針相遇的位置，當兩個指針相遇了后，讓其中一個指針從鏈表頭開始，一步兩步，一步一步似爪牙，似魔鬼的步伐。。。哈哈，打住打住。。。此時再相遇的位置就是鏈表中環(huán)的起始位置，為啥是這樣呢，這里直接貼上熱心網友「飛鳥想飛」的解釋哈，因為快指針每次走2，慢指針每次走1，快指針走的距離是慢指針的兩倍。而快指針又比慢指針多走了一圈。所以 head 到環(huán)的起點+環(huán)的起點到他們相遇的點的距離 與 環(huán)一圈的距離相等?，F在重新開始，head 運行到環(huán)起點 和 相遇點到環(huán)起點 的距離也是相等的，相當于他們同時減掉了 環(huá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

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

最新評論