[Leetcode] 876. Middle of the Linked List (鏈表的中間節點) 題解紀錄

題目:

Middle of the linked list (鏈表的中間節點)

難度:

簡單

題目要求:

題目給定一個非空的單鏈表，返回鏈表的中間節點。

如果鏈表有兩個中間節點，則返回第二個中間節點。

解題思路:

因為題目給定的是單向鏈表(Linded List)，所以我們只能透過迴圈的方式一個一個取得鏈表所有節點的資料。

那這題要怎麼解決呢?

可以透過雙指針的方式來解決。

想像一下，當兩個人開始同時走一條路，而第一個人的速度正好是第二個人速度的兩倍，所以當第一個人走到終點的時候，第二個人剛好會走到路途的正中間。

依照上面的思路，我們可以知道當快指針的速度是慢指針兩倍的時，快指針走到尾部，慢指針也剛好會到鏈表的正中間。