iT邦幫忙

2024 iThome 鐵人賽

DAY 7
0

Given the head of 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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.

給定一個linked list的head,返回linked list中cycle開始的node。如果linked list中没有cycle,回傳 null。
Linked list中存在cycle的條件是,linked list中的某個node可以透過不斷跟隨 next 指針再次被找到。内部使用 pos 來表示尾節點的 next 連接到的node的索引(0-index為基礎)

( → 這句話的意思就是:如果linked list中有cycle的話,那麼pos就是整個cycle的起始位置)。

如果沒有循環,pos 的值等於 -1。請注意,pos 並非作為參數傳遞。
請勿修改linked list。

題目範例如下
https://ithelp.ithome.com.tw/upload/images/20240818/20168667C8JtSY2ejm.png

https://ithelp.ithome.com.tw/upload/images/20240818/20168667RI0iV8DGhc.png

https://ithelp.ithome.com.tw/upload/images/20240818/20168667G8ZSKhCMaw.png


對於這題題目,一開始一直卡在要怎麼找到cycle的起始點這個問題上面,沒有把他跟快慢指針聯想在一起,只是按照自己的直覺,先整理出以下幾點:

  1. 首先,要確認有沒有cycle存在
  2. 如果有cycle,要如何知道從哪一個節點開始cycle循環的?

後來找到了Floyd Cycle Detection Algorithm(又稱為龜兔賽跑算法(Tortoise and Hare Algorithm),解決了以上兩個問題。

龜兔賽跑算法中,只要烏龜和兔子從起點開始向前奔跑,兩位選手都會 往同一方向 一路跑到終點,那這就表示這條賽道,是一直線通到終點,中間是沒有繞圈的,如下圖:
(烏龜 = 慢指針 , 兔子 = 快指針)
https://ithelp.ithome.com.tw/upload/images/20240818/20168667vOxuojM4a4.png

如果在賽道中,兔子雖然一路跑在烏龜前頭,但因為賽道的在距離賽道起點 X 的地方,繞了一個彎,並且繞回前面原本的繞彎處,但是在比賽規則中,烏龜跟兔子都只能向前跑,所以速度較慢的烏龜最後還是在繞彎處遇到跑得快的兔子。

因為兔子跑的速度是烏龜的兩倍,所以跑的距離也是烏龜的兩倍。

利用以上幾點,可以求得整條賽道開始繞彎的位置。
咦? 怎麼突然跳到結論? 我們來看看下面的圖示
https://ithelp.ithome.com.tw/upload/images/20240818/20168667MjWSQMwHZr.png

1.由上圖可以得到以下結論:

烏龜走的步數 * 2 = 兔子走的步數
      2 * (X+A) = X+2A+B               
     得到→    X = B 

2.承上,因X=B代表
只要烏龜從head出發走X步、兔子從node 2(相遇點)出發走B步,
也就是兩指針走相同距離便會在node 1相遇(cycle起始點)

講白話文就是,用烏龜跟兔子的速度歸納出:
1.烏龜跟兔子相遇的位置 與 賽道開始繞彎的位置
2.賽道起點 與 賽道開始繞彎的位置
1.2.距離是一樣的
所以這時,只要讓烏龜跟兔子兩個選手,分別用 一樣的速度,各自從賽道起點、相遇點 同時出發,相遇的中點,就會是 賽道開始繞彎的位置

解釋完概念,回到解題

  • 步驟 1. 設定兩個快慢指針,快指針每次移動的速度是慢指針的兩倍
  • 步驟 2. 先找到兩指針相遇的node 2位置,使用while迴圈檢查快指針要移動的下一個node是否存在
    • 步驟 2-1. 若存在,每次讓快指針往前移動兩步、慢指針往前移動一步
      • 步驟 2-1-1. 若快慢指針相遇(表示已找到相遇點),讓慢指針回到head的位置重新出發
      • 步驟 2-1-2. 接下來讓慢指針與快指針分別從head及相遇點用相同的速度出發
        • 步驟 2-1-2-1.若兩者相遇,則代表找到cycle的起點,回傳當下node位置
  • 步驟 3. 下一個node若不存在,表示linked list沒有cycle,回傳null

來看code

var detectCycle = function(head) {
    // set slow pointer
    let slow = head;
    // set fast pointer
    let fast = head;
    // find the position of node 2 (where two pointers meet)
    while(fast && fast.next && fast.next.next){ // while the next node that the fast pointer will move to exists
        slow = slow.next;
        fast = fast.next.next;
        // now pointer2 is at node 2(the meeting point)
        if (fast === slow) {
             // find the position of node 1 (where the cyle starts)
            slow = head;
            while (slow != fast){
                slow = slow.next;
                fast = fast.next; 
            }
            return fast;
        }
    }
    // if there is no cycle
    return null;
};

Reference:
https://hackmd.io/@PeterLei/leetcode142


上一篇
[Day6] Happy Number
下一篇
[Day8] Pattern - Sliding Window
系列文
刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言