Coding interview problems › Linked Lists

🔗 Linked Lists Medium

Reorder List

Reorder List explained: find the middle, reverse the second half and interleave the two halves in place, O(n) time, O(1) space. Tested Python and a live visual.

Also searched as: reorder linked list L0 Ln L1 Ln-1 · fold a linked list · interleave first and reversed second half

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Practise the reverse mode in the linked list lab until prev, cur and next feel automatic, since step 2 of this problem is exactly that reversal.

Open the playground →

The problem

Given a linked list L0 -> L1 -> ... -> Ln, rearrange its nodes in place into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ..., alternating from the front and the back. Change the links, not the node values.

Input1 -> 2 -> 3 -> 4 -> 5
Output1 -> 5 -> 2 -> 4 -> 3
Input1 -> 2 -> 3 -> 4
Output1 -> 4 -> 2 -> 3

The key insight

The pattern takes from the front and the back alternately, but a singly linked list cannot walk backwards. So make the back half walk forwards: split the list at its middle, reverse the second half, and then zip the two halves together one node from each side at a time. It is three classic moves glued together.

Brute force first: Putting all nodes in a Python list and relinking them with two indices from the ends works in O(n) time but uses O(n) extra space.

Step-by-step approach

  1. Find the end of the first half with slow and fast pointers (stop when fast.next or fast.next.next is None).
  2. Cut the list after slow and reverse the second half.
  3. Take first = head and second = head of the reversed half.
  4. While second exists, save both next pointers, link first -> second -> first.next, and advance both.
  5. The first half is equal in length or one node longer, so it absorbs the last node naturally.

Python solution

PYTHON 3tested
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


def reorder_list(head):
    if not head or not head.next:
        return head
    slow, fast = head, head                 # 1. find end of first half
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    prev, cur = None, slow.next             # 2. reverse the second half
    slow.next = None
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    first, second = head, prev              # 3. interleave
    while second:
        n1, n2 = first.next, second.next
        first.next, second.next = second, n1
        first, second = n1, n2
    return head

Complexity

TimeO(n)
SpaceO(1)

Finding the middle, reversing and merging are each one pass over at most n nodes, and only a handful of pointers are used.

Common mistakes

Frequently asked questions

What is the time and space complexity of Reorder List?

O(n) time with three linear passes, and O(1) extra space because all changes are pointer rewires in place.

Why reverse the second half instead of using a stack?

A stack of the second-half nodes also works and is easy to reason about, but costs O(n) extra space. Reversing in place gets the same back-to-front order in O(1) space.

Why stop the fast pointer at fast.next.next?

That leaves slow on the first middle, so the first half is the same length as the second or one node longer, which is exactly what the interleaving loop expects.

Which problems reuse these building blocks?

Palindrome Linked List uses find-middle plus reverse, and merge sort on a linked list uses find-middle plus merge.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.