題目網址：https://leetcode.cn/problems/middle-of-the-linked-list/

題意：返回 linked list 的中點, 若 linked list 的 node 數為偶數, 則返回第二個中點。

Solution：

想法：利用 Two Pointers
slow 一次走一步, fast 一次走兩步, 當 fast 走到 NULL 時, slow 剛好走到中點

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;

        // 當 n 為偶數時, 跳出迴圈是因為 fast == NULL
        // 當 n 為奇數時, 跳出迴圈是因為 fast->nxt = NULL
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list 中 $\dfrac{n}{2}$ 個元素
  • space：$O(1)$ ➔ 只需要常數空間