> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/linked-list/143.-reorder-list.md).

# 143. Reorder List

Given a singly linked list *L*: *L*0→*L*1→…→*Ln*-1→*L*n,\
reorder it to: *L*0→*Ln*→*L*1→*Ln*-1→*L*2→*Ln*-2→…

You may **not** modify the values in the list's nodes, only nodes itself may be changed.

**Example 1:**

```
Given 1->2->3->4, reorder it to 1->4->2->3.
```

**Example 2:**

```
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
```

```cpp
// Iteration with 3 passes
void reorderList(ListNode* head) { // time: O(n); space: O(1)
    if (!head || !head->next || !head->next->next) return;
    // Use fast & slow pointers to find the middle node of the list
    ListNode *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;
    // Reverse the second half list
    ListNode *cur = mid, *pre = nullptr, *nex = nullptr;
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    // Reorder processing
    // pre is the head of the second half list
    ListNode *p1 = head, *p2 = pre;
    while (p1 && p2) {
        nex = p1->next;
        p1->next = p2;
        p2 = p2->next;
        p1->next->next = nex;
        p1 = nex;
    }
}
```

```cpp
// Stack
void reorderList(ListNode* head) { // time: O(n); space: O(n)
    if (!head || !head->next || !head->next->next) return;
    stack<ListNode*> st;
    ListNode* cur = head;
    while (cur) {
        st.push(cur);
        cur = cur->next;
    }
    int cnt = (st.size() - 1) / 2;
    cur = head;
    while (--cnt >= 0) {
        ListNode* t = st.top(); st.pop();
        ListNode* nex = cur->next;
        cur->next = t;
        t->next = nex;
        cur = nex;
    }
    st.top()->next = nullptr; // remember to cut the list to avoid cyclic list
}
```