資訊專欄INFORMATION COLUMN
摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數(shù)是的兩倍。
Time：2019/4/8
Title: Linked List Cycle II
Difficulty: medium
Author:小鹿
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.
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表。
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)鏈表的位置。1、首先，先判斷該單鏈表是否存在循環(huán)鏈表？用兩個快慢指針（fast、slow）分別指向鏈表的頭部，fast 每次移動兩步，slow 每次移動一步，fast 移動的步數(shù)是 slow 的兩倍。
2、當(dāng) slow 與 fast 發(fā)生重合的時候，則存在鏈表。（slow 遍歷完單鏈表一遍，fast 遍歷了單鏈表兩遍，2 倍的關(guān)系，如果 pos = 0 時，正好在頭結(jié)點重合）。
3、如果 pos > 0 的時候。也就是說單鏈表中存在環(huán)，slow 到與 fast 指針重合的地方走過的路徑為 n，fast 走過的路徑是 slow 的兩倍也就是 2n 。如果此時讓 fast 每次走一步，走 n 步之后還會回到重合點。
4、那么怎么知道環(huán)接入的位置呢？這里稍微用的到點數(shù)學(xué)知識，看下圖：
當(dāng) fast 指針和 slow 指針重合時，我們在聲明一個 q 指針來計算到環(huán)結(jié)點的距離，因為 fast 改為每次移動一步，且 q 也要移動一步，fast 與 q 重合的地方就是環(huán)的接入點。（因為 slow 走過的路徑和 fast 走過的路徑相同，其中不重合的地方就是接入點）
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
//判斷頭結(jié)點是否為 null
if(head == null || head.next == null){
return null;
}
let fast = head;
let slow = head;
while(fast !== null && fast.next !== null){
fast = fast.next.next;
slow = slow.next;
//查找接入點
if(fast == slow){
slow = head;
while(slow !== fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
};
歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/103391.html
摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。兩種方法哈希表哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...
摘要：如果鏈表無環(huán)，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。兩種方法哈希表哈希表添加節(jié)點時只要發(fā)現(xiàn)節(jié)點已經(jīng)存在了，證明就有環(huán)形鏈表。 給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該...
摘要：小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表，沒遍歷一個節(jié)點就要在哈希表中判斷是否存在該結(jié)點，如果存在，則為環(huán)否則，將該結(jié)點插入到哈希表中繼續(xù)遍歷。 Time：2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿 題目：Linked List Cycle I Given a linked list, determine ...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 2066·2021-11-22 13:52
閱讀 991·2021-11-17 09:33
閱讀 2719·2021-09-01 10:49
閱讀 2853·2019-08-30 15:53
閱讀 2665·2019-08-29 16:10
閱讀 2438·2019-08-29 11:31
閱讀 1364·2019-08-26 11:40
閱讀 1877·2019-08-26 10:59
