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