Contents

[Golang][Leetcode][linkedList]刷題系列-142-尋找linked-list cycle起始點


142. Linked List Cycle II


Level : Medium

原題連結 : Click

題目 :

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.


Example :

Note

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.


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.


Input: head = [1], pos = -1

Output: no cycle

Explanation: There is no cycle in the linked list.


題目說明 :

  • 其實這題考察的不只對linked-list的掌握度,更重要的是考察對數學的敏銳度,我自己第一次做的時候也是參考其他高手的程式碼,再自己消化
  • 首先呢,題目其實是給一個linked-list,此linked-list有可能會有cycle,也可能沒有,若有cycle的話需要返回該cycle起始點的node,也就是cycle的進入點,如下圖

linked-list

解題思路 :

  • 這邊的解法我們採用two pointers的解法,一個fast,一個slow
  • fast從head出發一次走2個node,slow從head的出發一次走1個node
  • 這樣設定有兩個好處
    1. 若是此linked-list有cycle他們必然會撞在一起,若是沒有fast會先抵達nil,結束程式,可以用來判斷是否含有cycle
    2. 若是有cycle,可以取得他們最後相遇的node(它的功用可能不那麼直覺,所以須要看接下來的公式推導,加油!)

linked-list

  • 定義: x = headcycle進入點 的距離 y = cycle進入點相遇點 的距離 z = 相遇點cycle進入點 的距離 n = fast走cycle幾圈後與slow相遇 (fast繞cycle n 圈後與slow相遇)

  1. 假設 n = 1,fast走了1圈後相遇,fast總共走了 x + (y+z) + y 的距離

  2. 假設 n = 2,fast走了2圈後相遇,fast總共走了 x + 2(y+z) + y 的距離

  3. 假設 n = 3,fast走了3圈後相遇,fast總共走了 x + 3(y+z) + y 的距離

  4. 以此類推,若slow與fast相遇,且fast每次走的步數是slow的兩倍,可以得到 2(x+y) = x + n(y+z) + y


這邊有些朋友可能會有些許的疑問關於為什麼slow一定只有 x+y,有可能slow已經走完1圈後才在第2圈遇到fast阿?,甚至更多圈啊?

  • 這邊用一個簡單的例子跟大家說明:
    1. 先講一個既定的事實,當slow出發抵達cycle進入點2時,這時fast會在哪? 肯定是在cycle裡的某個位置!,且已經走過進入點1,正邁向進入點2
    2. 這代表說假設cycle一圈是a個node然後fast距離走到進入點2是b個node,b必小於a
    3. slow經過進入點2後,需要走a個node才能進入點3,fast則是要走b個node抵達進入點2,再走a個node到進入點3,fast的速度是slow的兩倍
    4. 所以,可以看出 (b+a)/2必小於a,所以slow還沒到進入點3前一定會被fast趕上,故我們可以斷然說slow肯定還走不完1圈就會就會與fast相遇
    5. 2(x+y) = x + n(y+z) + y 成立!

  • 此式子經過移項後,可以得到 x = n(y+z) -y,一樣我們幫n帶一些數字進去

    1. 假設 n = 1,fast走了1圈後相遇,x = z

    2. 假設 n = 2,fast走了2圈後相遇,x = (y+z) + z

    3. 假設 n = 3,fast走了3圈後相遇,x = 2(y+z) + z


  • 可以由圖中知道,y+z代表一圈,所以不管fast走幾圈相遇,其相遇點就是同一個node
  • 這時候再看看 n = 1 時, x = z ,回顧一下,x為headcycle進入點的距離,z為相遇點cycle進入點的距離
  • 這時候不能看出當我們找到相遇點時,再設一個pointer在head出發,另一個pointer從fast與slow的相遇點出發,最後就會cycle進入點相遇
  • 就可以得到題目所需要的答案,經過兩個步驟的尋找 先找fast與slow相遇點,再找cycle的進入點

以下是我自己的解法 - time complexity: O(n) , space complexity: O(1)

Runtime: 4 ms, faster than 98.99% of Go online submissions for Linked List Cycle II.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    
   
    var meet *ListNode
    
    fast, slow := head, head
    
    
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        
        if fast == slow {
            meet = fast
            
            for head != meet {
                
                head = head.Next
                meet = meet.Next      
            }
            return head
            
        }
    }
    return nil   
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!