---
# System prepended metadata

title: Leetcode 876. Middle of the Linked List
tags: [Linked Lists]

---

###### 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