143. Reorder List

---

My Solution

The Key Idea for Solving This Coding Question

如何以交叉編織的方式合併兩個單向鏈結串列 (第 38 ~ 53 行)

1. 假設 head 指向的單向鏈結串列長度小於或等於 head2 指向的單向鏈結串列。
2. 因為 it1->next 與 it2->next 皆必須改變所要指向的節點，所以先分別以 tmp1 與 tmp2 紀錄 it1->next 與 it2->next 目前所指向的節點。
3. 依題意將 it1->next 與 it2->next 指向應指向的節點。
   • it1->next 指向 it2。
   • it1 走到 tmp1 所在節點 (也就是 it1->next 原本指向的節點)。
   • 因為 head 指向的單向鏈結串列長度小於或等於 head2 指向的單向鏈結串列，所以要先檢查 it1 是否為 nullptr 。若 it1 為 nullptr ，表示合併結束，離開 while 迴圈。否則，繼續合併。
   • it2->next 指向 it1 。
   • it2 走到 tmp2 所在節點 (也就是 it2->next 原本指向的節點)。
4. 重複步驟 2 與 3 。

C++ Code

/**
 * 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 {
public:
    void reorderList(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return;
        }

        ListNode *preSlow = nullptr, *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        // Break the list.
        preSlow->next = nullptr;

        // Reverse the second half of the list.
        ListNode *head2 = nullptr;
        while (slow != nullptr) {
            ListNode *tmp = slow->next;
            slow->next = head2;
            head2 = slow;
            slow = tmp;
        }

        // Interweave the two lists.
        ListNode *it1 = head, *it2 = head2;
        while (true) {
            ListNode *tmp1 = it1->next;
            ListNode *tmp2 = it2->next;
            it1->next = it2;
            it1 = tmp1;
            if (it1 == nullptr) {
                // Because the list length of it1 is shorter 
                // than or equal to that of it2, it1 reaches
                // the end of its list first.
                break;
            }
            it2->next = it1;
            it2 = tmp2;
        }
    }
};

Time Complexity

$O(n)$

$n$ is the total number of nodes in the linked list.

Space Complexity

$O(1)$

Miscellaneous