[Leecode] Linked List Cycle 鏈表環

includecmath 發布于2019-08-14 12:27 / 420人閱讀

摘要：快慢指針法復雜度時間空間思路這是一道非常經典的雙指針題。如果快指針和慢指針相遇，則說明鏈表有環。代碼快慢指針法復雜度時間空間思路這題是基于上一題，上一題我們發現相遇后就返回了，而這里我們還要繼續找到環的起始點。

Linked List Cycle I

Given a linked list, determine if it has a cycle in it.

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

快慢指針法 復雜度

時間 O(N) 空間 O(1)

思路

這是一道非常經典的雙指針題。我們從頭設置一個快指針，一個慢指針。快指針一次走兩步，慢指針一次走一步，如果快指針走到了盡頭，則說明鏈表無環。如果快指針和慢指針相遇，則說明鏈表有環。為什么相遇就說明有環呢？設想一個有環鏈表，快慢指針最后都會走到環上，而這個環就像一個環形跑道一樣，慢指針在后面，快指針在前面，但實際上快指針也在追慢指針，希望能超慢指針一圈。他們在這個跑道上，總會有一天快指針追上了慢指針。我們不用擔心快指針跳過了慢指針，因為他們兩的速度差是1，所以她們倆在環上的距離總是每次減1，最后總能減到0。

代碼

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

2018/10

func hasCycle(head *ListNode) bool {
    fast := head
    slow := head
    // if fast.Next == nil and fast != slow, there can"t be a cycle
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Note: Do not modify the linked list.
Follow up: Can you solve it without using extra space?

快慢指針法 復雜度

時間 O(N) 空間 O(1)

思路

這題是基于上一題，上一題我們發現相遇后就返回true了，而這里我們還要繼續找到環的起始點。假設快慢指針在環上第k個節點相遇，而環的起點是鏈表第m個節點，環的總長度是n。此時慢指針再走n-k步就回到了環的開頭，而此時快指針已經走了m+k步。如果我們這時候將快指針放回起點，并讓它也一次走1步，這樣當兩個節點再次相遇時，相遇點就是環的起點。

代碼

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                // 找相遇點
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

GPU云服務器云服務器 Leecode linked Cycle jquery cycle js

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

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

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
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 141：環形鏈表 Linked List Cycle

摘要：給定一個鏈表，判斷鏈表中是否有環。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。哈希表解決重復問題最容易想到的數據結構就是哈希表，哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。給定一個鏈表，判斷鏈表中是否有環。為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。 Giv...

chenjiang3 2019-08-16 18:35 評論0 收藏0
LeetCode 141：環形鏈表 Linked List Cycle

摘要：給定一個鏈表，判斷鏈表中是否有環。示例輸入輸出解釋鏈表中有一個環，其尾部連接到第一個節點。哈希表解決重復問題最容易想到的數據結構就是哈希表，哈希表添加節點時只要發現節點已經存在了，證明就有環形鏈表。給定一個鏈表，判斷鏈表中是否有環。為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。 Giv...

ysl_unh 2019-07-31 11:28 評論0 收藏0