143. Reorder List

題目: 143. Reorder List

目描述

給定一個鏈結串列 L：

L_0 → L_1 → ... → L_{n-1} → L_n

請將其重新排列為：

L_0 → L_n → L_1 → L_{n-1} → L_2 → L_{n-2} → ...

要求：

• 原地重新排列，不得改變節點的值，只能調整節點的指標。

限制條件

• 鏈結串列的節點數量在 [1, 5 * 10^4] 之間。
• 1 <= Node.val <= 1000

解題思路

為了在 O(1) 的空間複雜度下原地完成重新排列，我們可以按照以下步驟進行：

1. 尋找鏈結串列的中點：
   • 使用 快慢指標法（Floyd's Tortoise and Hare Algorithm），讓 fast 指標每次前進兩步，slow 指標每次前進一步，當 fast 到達末端時，slow 就在中間位置。
2. 反轉後半部分的鏈結串列：
   • 從中點開始，反轉後半部分的鏈結串列，這樣可以方便我們從兩端同時進行合併。
3. 合併前半部分與反轉後的後半部分：
   • 逐一將反轉後的節點插入到前半部分中，完成重新排列。

程式碼

/**
 * 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) {}
 * };
 */
class Solution {
    ListNode* reverse(ListNode* head) {
        auto node = head;
        ListNode* prev = nullptr;
        while (node) {
            auto next = node->next;
            node->next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
public:
    void reorderList(ListNode* head) {
        auto fast = head;
        auto slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        auto mid = reverse(slow);

        while (mid && mid->next) {
            auto nextHead = head->next;
            auto nextMid = mid->next;
            head->next = mid;
            mid->next = nextHead;
            head = nextHead;
            mid = nextMid;
        }
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)
  • 分析：
    • 尋找中點：需要遍歷一次鏈結串列，時間複雜度為 O(n)。
    • 反轉後半部分：同樣需要遍歷一次，時間複雜度為 O(n)。
    • 合併兩部分：再次遍歷，時間複雜度為 O(n)。
    • 總共為 O(3n)，簡化為 O(n)。
• 空間複雜度：O(1)
  • 分析：除了使用固定數量的指標變數外，沒有使用額外的資料結構，符合原地操作的要求。