C++如何實現單鏈表中的環

這篇文章主要介紹“C++如何實現單鏈表中的環”，在日常操作中，相信很多人在C++如何實現單鏈表中的環問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++如何實現單鏈表中的環”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

單鏈表中的環

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?

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

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;
    }
};

到此，關于“C++如何實現單鏈表中的環”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！