yoruru的努力日記

876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

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

SOL：

這一題的直觀做法會是全部遍歷一次之後，找出中間點。

時間跟空間複雜度都是 O(n)，拜訪整個 linked list + 存下整個 linked list。

使用快慢指針的方式，快指針每次走兩步，慢指針每次只走一步，當快指針拜訪完整個 linked list 時，慢指針剛好只走到一半，時間複雜度維持 O(n)，需要拜訪完整個 linked list ；但空間複雜度可以降到 O(1)，不用去紀錄 linked list。

參考影片：leetcode 中文 | Middle of the Linked List | Fast and Slow pointers 基礎概念 4 - Python - LeetCode 876

我的程式碼：