題目

已經有一個不為空的singly-linked list，我們有此linked list的head node，要找出此linked list的middle node。
如果linked list的長度是偶數的話，在中間的有2個node，那就回傳第2個。

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

解法

1. 輸出到array

• 遍歷一次
• array能隨機存取，回傳中間的node

Time complexity O(n)

遍歷一次 = n

space complexity O(n)

array的空間佔 n

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> list;
        ListNode* curNode = head;
        while(curNode != nullptr){
            list.push_back(curNode);
            curNode = curNode->next;
        }
        return list[list.size()/2];
        
    }
};

2. One pointer (暴力走2次)

• 先遍歷一次linked list得到長度
• 算出中間值
• 再找到中間的node並回傳。

Time complexity O(n)

while遍歷一次+從頭走到中間的node n+n/2 ~= n

space complexity O(1)

紀錄size的值

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int listSize = 0;
        ListNode* curNode = head; 
        
        //先遍歷一次linked list得到長度
        while(curNode != nullptr){
            listSize++;
            curNode = curNode->next;
        }
        
        //算出中間值 (長度/2)
        int middleSize = listSize >> 1;
        
        //再找到中間的node，回傳
        curNode = head;
        while(middleSize--){
            curNode = curNode->next;
        }
        
        return curNode;
    }
};

3. Two pointer

• 第一個pointer稱作fast，用來遍歷的。
• 第二個pointer稱作slow，用來到中間node的。
• 因為是取中間node，每當fast往前走2個，slow就能往前走1個。
  比起一個pointer

Time complexity O(n)

while遍歷一次(這裡要注意fast是一次走2格) n/2 ~= n

space complexity O(1)

紀錄size的值
雖然時間複雜度同為n，相對於one pointer，n到超級大的時候還是比較快的，但n很大的話，應該考慮改用別的資料結構儲存。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};