C++實現(xiàn)LeetCode(142.單鏈表中的環(huán)之二)
[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。這里還是要設(shè)快慢指針,不過這次要記錄兩個指針相遇的位置,當(dāng)兩個指針相遇了后,讓其中一個指針從鏈表頭開始,一步兩步,一步一步似爪牙,似魔鬼的步伐。。。哈哈,打住打住。。。此時再相遇的位置就是鏈表中環(huán)的起始位置,為啥是這樣呢,這里直接貼上熱心網(wǎng)友「飛鳥想飛」的解釋哈,因為快指針每次走2,慢指針每次走1,快指針走的距離是慢指針的兩倍。而快指針又比慢指針多走了一圈。所以 head 到環(huán)的起點+環(huán)的起點到他們相遇的點的距離 與 環(huán)一圈的距離相等?,F(xiàn)在重新開始,head 運行到環(huán)起點 和 相遇點到環(huán)起點 的距離也是相等的,相當(dāng)于他們同時減掉了 環(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
類似題目:
參考資料:
https://leetcode.com/problems/linked-list-cycle-ii/
到此這篇關(guān)于C++實現(xiàn)LeetCode(142.單鏈表中的環(huán)之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)單鏈表中的環(huán)之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c++項目中后綴名vcxproj和sln的區(qū)別及說明
這篇文章主要介紹了c++項目中后綴名vcxproj和sln的區(qū)別及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05利用C語言實現(xiàn)任務(wù)調(diào)度的示例代碼
這篇文章主要為大家詳細介紹了如何利用純C語言實現(xiàn)任務(wù)調(diào)度(可用于STM32、C51等單片機),文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下2023-04-04C++?LeetCode0547題解省份數(shù)量圖的連通分量
這篇文章主要為大家介紹了C++?LeetCode0547題解省份數(shù)量圖的連通分量示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-12-12Qt槽函數(shù)會被執(zhí)行多次的問題原因及解決方法
本文主要介紹了Qt槽函數(shù)會被執(zhí)行多次的問題原因及解決方法,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01