---
tags: leetcode
---

# [143. Reorder List](https://leetcode.com/problems/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
<!--
# Test Cases

[1,2,3,4]

[1,2,3,4,5]

[1]

[1,2]

[1,2,3]

-->