LeetCode 之 JavaScript 解答第142題 —— 環形鏈表 II（Linked Li

whidy 發布于2019-08-23 16:51 / 3186人閱讀

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。

Time：2019/4/8
Title: Linked List Cycle II
Difficulty: medium
Author:小鹿

題目：Linked List Cycle II

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.

給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。

說明：不允許修改給定的鏈表。

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?

Solve:

▉ 算法思路：

題目要求返回單鏈表中存在循環鏈表的位置。

1、首先，先判斷該單鏈表是否存在循環鏈表？用兩個快慢指針（fast、slow）分別指向鏈表的頭部，fast 每次移動兩步，slow 每次移動一步，fast 移動的步數是 slow 的兩倍。

2、當 slow 與 fast 發生重合的時候，則存在鏈表。（slow 遍歷完單鏈表一遍，fast 遍歷了單鏈表兩遍，2 倍的關系，如果 pos = 0 時，正好在頭結點重合）。

3、如果 pos > 0 的時候。也就是說單鏈表中存在環，slow 到與 fast 指針重合的地方走過的路徑為 n，fast 走過的路徑是 slow 的兩倍也就是 2n 。如果此時讓 fast 每次走一步，走 n 步之后還會回到重合點。

4、那么怎么知道環接入的位置呢？這里稍微用的到點數學知識，看下圖：

當 fast 指針和 slow 指針重合時，我們在聲明一個 q 指針來計算到環結點的距離，因為 fast 改為每次移動一步，且 q 也要移動一步，fast 與 q 重合的地方就是環的接入點。（因為 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) {
    //判斷頭結點是否為 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...

云服務器 GPU云服務器 javascript算法題匯編語言程序設計第二版課后題答案 javascript必問面試題 linked

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103391.html

LeetCode 142：環形鏈表 II Linked List Cycle II

摘要：如果鏈表無環，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。兩種方法哈希表哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該...

hoohack 2019-08-16 18:36 評論0 收藏0
LeetCode 142：環形鏈表 II Linked List Cycle II

摘要：如果鏈表無環，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。兩種方法哈希表哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該...

geekzhou 2019-07-31 11:29 評論0 收藏0
LeetCode 之 JavaScript 解答第141題 —— 環形鏈表 I（Linked Lis

摘要：小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表，沒遍歷一個節點就要在哈希表中判斷是否存在該結點，如果存在，則為環否則，將該結點插入到哈希表中繼續遍歷。 Time：2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿題目：Linked List Cycle I Given a linked list, determine ...

wangjuntytl 2019-08-23 16:49 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0