題目網址：https://leetcode.cn/problems/reorder-list/

題意：給一單向 linked list 的起始節點 head, 該 linked list 可表示為

L0 → L1 → … → Ln - 1 → Ln

將其重新排序為

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是單純改變節點內部的值, 必須進行實際的節點交換。

Solution：

想法：分成以下步驟

  • 找到 linked list 的中點, 按照 141. Linked List Cycle 的方法
    • 奇數時, mid 指向中點
    • 偶數時, mid 指向右中點
    • 因此, 最一開始要先讓 fast 先走一步, 這樣不管是奇偶數, mid 都會指向左中點
  • 重要：截斷兩個 list ➔ mid->next = nullptr（容易忘記這步）
  • reverse 右半部分 Ln → Ln - 1 → Ln - 2 → ...
  • merge 左半和右半
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *mid = get_mid(head); // 得到第一個中點
        ListNode *right = mid->next; // 得到右半部分
        mid->next = nullptr; // **重要** 截斷兩個 list
        right = reverse(right); // reverse 右半部分
        merge(head, right); // merge 左半和右半
    }

private:
    // // 找到中點; 若為偶數, 則返回第一個中點
    ListNode* get_mid(ListNode* head){
        // 先讓 fast 先走一步, 這樣偶數時, slow 才會是第一個中點
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverse(ListNode* head){
        ListNode *tail = head;
        ListNode *prev = nullptr, *nxt = nullptr;
        while (tail) {
            nxt = tail->next;
            tail->next = prev;
            prev = tail;
            tail = nxt;
        }
        return prev;
    }

    void merge(ListNode* l1, ListNode* l2){
        while (l1 && l2) {
            // 先儲存各自的 next
            ListNode *n1 = l1->next;
            ListNode *n2 = l2->next;

            // l1 下一個指向當前的 l2, 然後 l2 下一個指向 n1
            l1->next = l2;
            l2->next = n1;

            // 各自前進到下一個
            l1 = n1;
            l2 = n2;
        }
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需常數空間