###### tags: `Linked Lists`
# Leetcode 876. Middle of the Linked List

1. 問題描述
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.

2. Input的限制
* The number of nodes in the list is in the range [1, 100].
* 1 <= Node.val <= 100

3. 思考流程
* Output to Array
將 linked list 先走過一遍，過程中利用 ans 這個 list 儲存每個 node。結束後，將 ans 內索引值為 len(ans)//2 的 node 回傳，即可獲得 linked list 的 middle node。<br>

在時間複雜度上，因為需要走過 linked list 一遍，故 time complexity 為 O(N)。在空間複雜度上，因為需要 ans 這個 list 作為儲存 node 的載體，故 space complexity 是 O(N)。

Time Complexity: O(N); Space Complexity: O(N)

* Fast and Slow pointers
先準備 2 個 pointers。Slow pointer 逐個 node 進行遍歷；Fast pointer 則每 2 個 node 進行遍歷，當 fast pointer 走到了 linked list 的尾巴，同時 slow pointer 會走到 linked list 的中間，回傳 slow pointer 指向的 node 即可。<br>

在時間複雜度上，兩個兩個 node 進行遍歷，需要走過 linked list 一遍，故 time complexity 為 O(N)。在空間複雜度上，只使用到 2 個 pointers，故 space complexity 是 O(1)。

Time Complexity: O(N); Space Complexity: O(1)

4. 測試
* test 1
Input: head = [1,2,3]
Output: [2,3]
* test 2
Input: head = [1]
Output: [1]
* test 3
Input: head = [1,2,3,4]
Output: [3,4]
* test 4
Input: head = []
Output: 回傳錯誤訊息，空 linked list 不存在 middle node