題目敘述
題目會給我們一個鏈結串列的起點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
