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

hoohack 發布于2019-08-16 18:36 / 2081人閱讀

摘要：如果鏈表無環，則返回。說明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。兩種方法哈希表哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。

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

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

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

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.

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環。

進階： 你是否可以不用額外空間解決此題？

Follow-up: Can you solve it without using extra space?

解題思路：

和上一道題比只多了一步判斷入環節點在哪。兩種方法：

哈希表：

哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。并且已存在的節點即為入環節點

雙指針：

畫了個圖幫助理解：

一快一慢雙指針開始從頭結點遍歷鏈表，快節點速度為2，慢節點速度為1：

相遇時：

慢節點走了：a+b

由于快指針速度是慢指針的2倍，快節點走了：2(a+b)

快慢節點相遇時快節點比慢節點剛好多走了一圈環形節點。快節點走了：(a+b)+(b+c)

列方程：2(a+b)=(a+b)+(b+c)

解得 a=c

也就是說：相遇節點到入環節點的長度和頭節點到入環節點的長度相等

可以得出結論，如果此時讓慢節點或快節點中的一個指向頭節點，另一個留在相遇節點，然后速度都為1，繼續遍歷鏈表，雙指針再次相遇時的節點剛好是入環節點。

注：為了理解方便，把長度 b 定為上半部分長度，實際上 b 應該為快慢節點相遇時慢節點繞過環形鏈表的總長度

哈希表解題：

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;//如果是空鏈表直接返回
        Set nodeSet = new HashSet<>();//構造哈希表
        while (head.next != null) {//鏈表下一個不為空
            if (nodeSet.contains(head)) return head;//哈希表包含該節點則存在環形鏈表
            nodeSet.add(head);//加入節點
            head = head.next;//下移一位
        }
        return null;
    }
}

Python：

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        hashSet=set()#構造集合
        while(head.next is not None):
            if head in hashSet:#是否已存在
                return head
            hashSet.add(head)
            head=head.next
        return None

雙指針解題：

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {//快指針及其下一位是否為null
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//如果相同，存在環形鏈表
                slow = head;//指向頭節點
                while (slow != fast) {//繼續遍歷，再次相遇時的節點即為入環節點
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Python：

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return None
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

歡迎關注公眾號：愛寫Bug（ID：iCodeBugs）

云服務器 GPU云服務器 II quartus ii ii6 ii7

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

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

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

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

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

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿題目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 評論0 收藏0
leetcode141-142. Linked List Cycle I & II

摘要：題目要求這道題目要求判斷一個鏈表中是否有環，如果有環，就返回環中的第一個節點。如果有環，就會重復遇到這個指向的節點。則該鏈表有環，且該節點就是環的起始節點。但是這個方法會毀壞原來鏈表的數據結構。題目要求 Given a linked list, return the node where the cycle begins. If there is no cycle, return n...

張巨偉 2019-08-16 10:40 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0