# Reorder List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reorder-list)
Canonical: https://scaleengineer.com/dsa/problems/reorder-list
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List, Stack
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [LinkedIn](https://scaleengineer.com/companies/linkedin), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
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:**

![](https://assets.glich.co/dsa/reorder-list/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/reorder-list/image1.jpg) 

**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`

# Approaches
## Using an Auxiliary List
This approach simplifies the problem by converting the linked list into a more flexible data structure like an `ArrayList`. By storing all nodes in a list, we can easily access any node by its index. This allows us to use two pointers, one at the beginning and one at the end, to rebuild the linked list in the desired order.
**Time:** O(N) · **Space:** O(N)
**Pros:** Conceptually simple and easy to implement.; Avoids complex pointer manipulation during traversal.
**Cons:** Requires extra space proportional to the number of nodes, which can be significant for large lists.; Generally not the expected solution in an interview setting where in-place solutions are preferred.
### Explanation
First, we iterate through the original linked list from head to tail. During this traversal, we add each node to an `ArrayList`. After the list is fully stored, we can re-wire the `next` pointers. We use two integer indices, `left` starting at 0 and `right` starting at `size - 1`. We iterate as long as `left < right`. In each step, we link the node at `left` to the node at `right` (`nodes.get(left).next = nodes.get(right)`). Then, we increment `left`. To continue the chain, we link the node at `right` to the new `left` node (`nodes.get(right).next = nodes.get(left)`). Then we decrement `right`. This process continues until the pointers meet or cross. Finally, the `next` pointer of the last node in the new sequence (which will be at index `left` when the loop terminates) must be set to `null` to signify the end of the list.

```java
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 1. Store all nodes in a list
        List<ListNode> nodes = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            nodes.add(current);
            current = current.next;
        }

        // 2. Re-wire the nodes using two pointers
        int left = 0, right = nodes.size() - 1;
        while (left < right) {
            nodes.get(left).next = nodes.get(right);
            left++;
            if (left == right) {
                break;
            }
            nodes.get(right).next = nodes.get(left);
            right--;
        }
        
        // 3. Set the last node's next to null
        nodes.get(left).next = null;
    }
}
```
### Algorithm
- Create an `ArrayList` to store the nodes of the linked list.
- Traverse the linked list from the `head` and add each node to the `ArrayList`.
- Initialize two pointers, `left = 0` and `right = list.size() - 1`.
- Iterate while `left < right`:
  - Set the `next` of the node at index `left` to point to the node at index `right`.
  - Increment `left`.
  - If `left` becomes equal to `right`, break the loop (for odd length lists).
  - Set the `next` of the node at index `right` to point to the node at the new index `left`.
  - Decrement `right`.
- Set the `next` pointer of the last node in the reordered sequence (at index `left`) to `null`.

## Recursive In-place Reordering
This approach uses recursion to traverse the list to the end and then reorders the nodes as the recursion unwinds. The call stack implicitly keeps track of the nodes from the end of the list, which we can then interleave with nodes from the beginning, tracked by a separate pointer.
**Time:** O(N) · **Space:** O(N)
**Pros:** Performs the reordering in-place without an explicit auxiliary data structure.
**Cons:** The space complexity is O(N) due to the recursion call stack, which can lead to a StackOverflowError for very long lists.; The logic can be less intuitive than the iterative approaches.
### Explanation
The core idea is to use the function call stack to our advantage. We define a recursive function that traverses to the end of the list. When the recursion starts to unwind, we are effectively processing nodes from tail to head. We maintain a global or class-level pointer, `left`, initialized to the `head` of the list. This pointer will move from the beginning towards the middle. The recursive function takes the current `right` node as its parameter. The base case is when `right` is `null`. After the recursive call `recurse(right.next)` returns, we are at node `right`, and the `left` pointer is at the corresponding node from the beginning. We can then perform the re-wiring. We need a mechanism to stop the re-wiring process once the `left` and `right` pointers meet or cross in the middle of the list. A boolean flag or a direct comparison of `left` and `right` pointers can be used for this. Once the middle is reached, we terminate the list by setting the `next` pointer of the middle/last re-wired node to `null` and signal all parent recursive calls to stop further processing.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode left;
    private boolean stop;

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        this.left = head;
        this.stop = false;
        recurse(head);
    }

    private void recurse(ListNode right) {
        if (right == null) {
            return;
        }

        recurse(right.next);

        if (this.stop) {
            return;
        }

        if (this.left == right || this.left.next == right) {
            right.next = null;
            this.stop = true;
            return;
        }

        ListNode temp = this.left.next;
        this.left.next = right;
        right.next = temp;
        
        this.left = temp;
    }
}
```
### Algorithm
- Initialize a class member pointer `left` to `head` and a boolean `stop` to `false`.
- Define a recursive function `recurse(right)` that takes the current node as an argument.
- The base case for the recursion is `right == null`.
- In the recursive step, call `recurse(right.next)`.
- After the recursive call returns, check the `stop` flag. If `true`, return immediately.
- Check if the reordering is complete. This happens when `left` and `right` pointers meet (for odd-length lists) or `left.next` points to `right` (for even-length lists). If so, set the `next` of the appropriate node to `null`, set `stop` to `true`, and return.
- If not complete, perform the re-wiring:
  - Store `left.next` in a temporary variable.
  - Set `left.next` to `right`.
  - Set `right.next` to the temporary variable.
  - Advance `left` to its new position (`left = temp`).

## In-place Reorder with List Splitting and Reversing
This is the most efficient and standard approach. It solves the problem in-place with constant extra space. The strategy involves three main steps: finding the middle of the list, reversing the second half of the list, and then merging the first half with the reversed second half.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal solution with O(1) space complexity.; It's a robust and common pattern for solving linked list problems.
**Cons:** The implementation is more complex than the auxiliary space approach, involving multiple distinct steps and careful pointer manipulation.
### Explanation
**1. Find the Middle Node:** We use the classic "slow and fast pointer" technique. A `slow` pointer moves one step at a time, while a `fast` pointer moves two steps. When the `fast` pointer reaches the end of the list, the `slow` pointer will be at the middle node (or the end of the first half).

**2. Split and Reverse the Second Half:** Once the middle is found, we split the list into two halves. The `next` pointer of the `slow` node is set to `null`. The node originally after `slow` becomes the head of the second half. We then reverse this second half using a standard iterative reversal algorithm (using `prev`, `curr`, `next` pointers).

**3. Merge the Two Halves:** Now we have two independent lists: the first half starting at `head`, and the reversed second half. We can merge them by interleaving their nodes. We take one node from the first list, then one from the second, and link them together, advancing the pointers in each list until the second list is exhausted.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 1. Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Reverse the second half of the list
        ListNode secondHead = slow.next;
        slow.next = null; // Split the list
        
        ListNode prev = null;
        ListNode curr = secondHead;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        // 'prev' is now the head of the reversed second half

        // 3. Merge the two halves
        ListNode firstHead = head;
        ListNode reversedSecondHead = prev;
        while (reversedSecondHead != null) {
            ListNode temp1 = firstHead.next;
            ListNode temp2 = reversedSecondHead.next;

            firstHead.next = reversedSecondHead;
            reversedSecondHead.next = temp1;

            firstHead = temp1;
            reversedSecondHead = temp2;
        }
    }
}
```
### Algorithm
- **Find Middle:** Use a slow and a fast pointer to find the end of the first half of the list. The `slow` pointer will be the last node of the first half.
- **Split:** The node after `slow` is the head of the second half. Set `slow.next = null` to break the list into two.
- **Reverse:** Iteratively reverse the second half of the list.
- **Merge:** Initialize two pointers, `p1` to the head of the first half and `p2` to the head of the reversed second half.
- Iterate while `p2` is not null:
  - Store the next nodes: `temp1 = p1.next`, `temp2 = p2.next`.
  - Link `p1` to `p2`: `p1.next = p2`.
  - Link `p2` to `p1`'s original next: `p2.next = temp1`.
  - Move pointers forward: `p1 = temp1`, `p2 = temp2`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public void ReorderList ( ListNode head ) { ListNode slow = head ; ListNode fast = head ; while ( fast . next != null && fast . next . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } cur = head ; while ( pre != null ) { ListNode t = pre . next ; pre . next = cur . next ; cur . next = pre ; cur = pre . next ; pre = t ; } } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList ( ListNode head ) { ListNode fast = head , slow = head ; while ( fast . next != null && fast . next . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } cur = head ; while ( pre != null ) { ListNode t = pre . next ; pre . next = cur . next ; cur . next = pre ; cur = pre . next ; pre = t ; } } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */ var reorderList =
  function (head) {
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    let cur = slow.next;
    slow.next = null;
    let pre = null;
    while (cur) {
      const t = cur.next;
      cur.next = pre;
      pre = cur;
      cur = t;
    }
    cur = head;
    while (pre) {
      const t = pre.next;
      pre.next = cur.next;
      cur.next = pre;
      cur = pre.next;
      pre = t;
    }
  };

```

### CPP

```cpp
/** * 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 * fast = head ; ListNode * slow = head ; while ( fast -> next && fast -> next -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } ListNode * cur = slow -> next ; slow -> next = nullptr ; ListNode * pre = nullptr ; while ( cur ) { ListNode * t = cur -> next ; cur -> next = pre ; pre = cur ; cur = t ; } cur = head ; while ( pre ) { ListNode * t = pre -> next ; pre -> next = cur -> next ; cur -> next = pre ; cur = pre -> next ; pre = t ; } } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def reorderList ( self , head : Optional [ ListNode ]) -> None : fast = slow = head while fast . next and fast . next . next : slow = slow . next fast = fast . next . next cur = slow . next slow . next = None pre = None while cur : t = cur . next cur . next = pre pre , cur = cur , t cur = head while pre : t = pre . next pre . next = cur . next cur . next = pre cur , pre = pre . next , t
```