## [143\. Reorder List](https://leetcode.com/problems/reorder-list/)

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

_Reorder the list to be on the following form:_

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

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

**Example 1:**


**Input:** head = \[1,2,3,4\]
**Output:** \[1,4,2,3\]

**Example 2:**


**Input:** head = \[1,2,3,4,5\]
**Output:** \[1,5,2,4,3\]

**Constraints:**

- The number of nodes in the list is in the range `[1, 5 * 104]`.
- `1 <= Node.val <= 1000`

/**
 * 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) {
        // 使用快慢指針尋找中間節點
        // 快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針剛好到達中間節點。
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 將中間節點之後的 linked list 反轉，以便後續可以交錯合併。
        ListNode* cur = slow->next;
        ListNode* prev = nullptr;
        
        while(cur) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        // 斷開前後兩個部分
        slow->next = nullptr;
        
        // 將前半部分和反轉後的後半部分交錯合併。
        ListNode *first = head;
        second = prev;
        while(second) {
            ListNode* node1 = first->next;
            ListNode* node2 = second->next;
            first->next = second;
            second->next = node1;
            first = node1;
            second = node2;
        }
    }
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::