一魚多吃 用雙指針找出串列的中點 Middle of Linked list_Leetcode #876

Luke van Zyl on Unsplash

題目敘述

題目會給我們一個鏈結串列的起點head，要求我們找出這個串列的中點。

註:

如果串列長度是偶數，就回傳中間偏右的那個節點。

例如:

1 -> 2 -> 3 回傳中點為2

1 -> 2 -> 3 -> 4 ->5 -> 6 回傳中點為4

詳細的題目可在這裡看到

測試範例

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

約束條件

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

演算法

想像鏈結串列就是一條筆直的跑道，我們所要做的就是找出跑道的中點。

可以用雙指針的技巧找出來，在這邊用兩個跑著做比喻。

快的跑者每一回合跑兩單位長(想像方便，也可以假想成兩公尺/秒)，

慢的跑者每一回合跑一單位長(想像方便，也可以假想成一公尺/秒)。

兩者同時起跑，當快的跑者抵達終點時，慢的跑者會剛好位在整條跑道的中央點。

image

程式碼

class Solution:
　def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:

　　slow = fast = head

　　while fast and fast.next:
			
		　# fast runner​
　　　fast = fast.next.next
　　　# slow runner​
　　　slow = slow.next

　　return slow

複雜度分析

時間複雜度:

O( n )

從頭到尾，利用fast runner 快跑者拜訪一遍，長度和原本的串列一樣長O(n)

O( 1 )

使用到的變數都是臨時變數，皆為固定尺寸大小，為常數等級O(1)。

關鍵知識點

聯想到跑道模型和快、慢雙指針的技巧，可以用雙指針優雅地在一次迴圈拜訪的條件下找出串列的中點位置。

Reference:

[1] Python/JS/Java/Go/C++ O(n) by two-pointers 90%+ [w/ Diagram] - Middle of the Linked List - LeetCode