Reorder List

Table of Contents +

Reorder List looks like one puzzle, but it is really three small skills joined together. The interviewer wants to see if you can break a hard problem into pieces you already know. So if you can find the middle, reverse a list, and merge two lists, you can solve this one.

🎯 The Problem

You must weave a list from both ends into a new order. Here are the rules.

  • You get a singly linked list. Each node points only to the next one.
  • Rearrange the nodes into first, last, second, second-last, and so on.
  • For 1 -> 2 -> 3 -> 4, the new order is 1 -> 4 -> 2 -> 3.
  • You keep weaving from both ends toward the middle.
  • You must change the links themselves, not just the values.
Input:  1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3


Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Here is the chain drawn as nodes and the arrows that join them.

1

2

3

4

🐢 Approach 1: Array Copy With Two Pointers (Brute Force)

The idea in one line: copy nodes into an array, then link front to back walking inward.

The idea:

  • Copy every node into an array.
  • An array lets you grab any node by its index.
  • Put one pointer at the front and one at the back.
  • Link the front node to the back node, then step both toward the center.

How it works:

  • Keep weaving front then back until the two pointers meet.
  • That gives the first, last, second, second-last order.

Why it is weak:

  • You build a whole new array just to hold the nodes.
  • That uses extra memory equal to the size of the list, so O(n) space.
  • For a huge list that extra memory adds up.

Here is the array-copy code:

reorder_list_array_copy.py
def reorder_list(head):
    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.next


    left, right = 0, len(nodes) - 1
    dummy = ListNode(0)
    cur = dummy
    while left <= right:
        cur.next = nodes[left]
        cur = cur.next
        left += 1
        if left <= right:
            cur.next = nodes[right]
            cur = cur.next
            right -= 1
    cur.next = None

⚡ Approach 2: Find Middle, Reverse, Merge (Best)

The idea in one line: solve it in place with three small steps you already know.

The idea:

  • In place means reuse the same nodes and change only their links.
  • Step one: find the middle with slow and fast pointers.
  • Step two: reverse the back half so it points backward.
  • Step three: merge the two halves by weaving them together.

How it works:

  • The slow pointer moves one node. The fast pointer moves two nodes.
  • When fast reaches the end, slow sits right at the middle.
  • After reversing, the back half starts from the old last node.
  • Weave one front node, then one reversed back node, then repeat.

Why it is fast:

  • No extra array. Just pointer changes.
  • So the extra memory drops to O(1).
  • It still walks the list only a few times, so the time stays O(n).

Here is the three-step flow on the example list.

Split: 1 2 and 3 4

Reverse back: 4 3

Merge: 1 4 2 3

Steps to Solve

  1. If the list is empty or has one node, there is nothing to do, so return.
  2. Use slow and fast pointers to find the middle node.
  3. Cut the list into a front half and a back half at the middle.
  4. Reverse the back half so it starts from the old last node.
  5. Merge the two halves by taking one node from each, front then back, until both run out.

This Python version uses a small Node class and the find-middle, reverse, merge steps.

reorder_list.py
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None




def reorder(head):
    if not head or not head.next:
        return


    # find the middle with slow and fast pointers
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next


    # reverse the back half
    second = slow.next
    slow.next = None              # cut into two halves
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp


    # merge the two halves
    first, back = head, prev
    while back:
        f1 = first.next
        b1 = back.next
        first.next = back         # weave one back node in
        back.next = f1
        first = f1
        back = b1




def print_list(head):
    parts = []
    cur = head
    while cur:
        parts.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(parts))




head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
reorder(head)
print_list(head)

The output of the above code will be:

1 -> 4 -> 2 -> 3

Let us walk through the Python version line by line and see why each part is there.

The guard if not head or not head.next: return handles the tiny cases. An empty list or a one-node list is already in order. So we stop early and avoid crashing on missing nodes.

The lines slow, fast = head, head and the while fast.next and fast.next.next loop find the middle. The fast pointer covers two nodes for every one node the slow pointer covers. So when fast nears the end, slow has covered half the distance. That puts slow at the middle.

The line second = slow.next grabs the start of the back half. Then slow.next = None cuts the chain into two separate lists. Now the front half ends cleanly.

The reverse loop flips the back half. On each turn we save tmp = second.next so we do not lose the rest. Then second.next = prev turns the arrow backward. We slide prev and second forward. When the loop ends, prev holds the new head of the reversed back half.

The merge loop weaves the halves. We save the next front node in f1 and the next back node in b1 before we change any links. Then first.next = back drops a back node right after a front node. And back.next = f1 reconnects to the rest of the front. We step both pointers forward and repeat. That gives the first, last, second, second-last pattern.

⏱️ Time and Space Complexity

The array copy way walks the list once to build the array, so it is O(n) time, but it holds every node in extra memory, so it is O(n) space. The optimal way also walks the list a few times, which is still O(n) time, but it only moves pointers around, so it needs just O(1) extra space.

Approach Time Complexity Space Complexity
Array copy with two pointers O(n) O(n)
Find middle, reverse, merge O(n) O(1)

Tip

This problem is three classic patterns stacked together. Practice find-the-middle, reverse-a-list, and merge-two-lists on their own first. Then this question becomes easy, because you are just calling skills you already have.

🧩 Key Takeaways

  • ✅ Reorder List is really three smaller problems joined: find middle, reverse, merge.
  • ✅ The slow and fast pointer trick lands you on the middle in one pass.
  • ✅ Reversing the back half lets you reach the last nodes from the front.
  • ✅ Weaving one front node then one back node gives the first, last, second order.
  • ✅ Doing it in place keeps the extra memory at O(1).

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What order should the nodes be in after reordering 1 -> 2 -> 3 -> 4 -> 5?

    Why: You weave from both ends: first, last, second, second-last, and so on. That gives 1 -> 5 -> 2 -> 4 -> 3.

  2. 2

    How do the slow and fast pointers find the middle of the list?

    Why: Fast moves twice as fast as slow, so when fast reaches the end, slow is at the middle.

  3. 3

    Why do we reverse the back half of the list?

    Why: After reversing, the back half starts at the old last node, so weaving from both ends becomes simple.

  4. 4

    What is the space complexity of the optimal find-middle, reverse, merge solution?

    Why: The optimal solution changes links in place and uses only a few pointer variables, so it is O(1) extra space.

Score: 0 / 4

🚀 What’s Next?

Previous Remove the Nth Node from the End Next Add Two Numbers