LeetCode 143: Reorder List

Problem Restatement

We are given the head of a singly linked list.

The list can be written as:

L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln

We need to reorder it into:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

The reordering must be done in-place. We may change node links, but we may not modify node values. The function returns nothing. LeetCode states this exact in-place requirement for the problem.

Examples

Example 1:

1 -> 2 -> 3 -> 4

After reordering:

1 -> 4 -> 2 -> 3

Example 2:

1 -> 2 -> 3 -> 4 -> 5

After reordering:

1 -> 5 -> 2 -> 4 -> 3

Input and Output

Item	Meaning
Input	`head: Optional[ListNode]`
Output	Nothing
Operation	Modify the linked list in-place
Constraint	Node values must not be changed
Desired order	First node, last node, second node, second-last node, and so on

Function shape:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        ...

First Thought: Store Nodes in an Array

A simple solution is to store every node in an array.

Then use two pointers:

left = 0
right = n - 1

Connect:

nodes[left] -> nodes[right] -> nodes[left + 1] -> nodes[right - 1] ...

This is easy, but it uses O(n) extra space.

We can do the same reordering with O(1) extra space by changing the list structure directly.

Key Insight

The target order alternates between:

the first half in normal order
the second half in reverse order

For example:

1 -> 2 -> 3 -> 4 -> 5

Split into:

first half:  1 -> 2 -> 3
second half: 4 -> 5

Reverse the second half:

5 -> 4

Then merge alternately:

1 -> 5 -> 2 -> 4 -> 3

So the algorithm has three phases:

Find the middle.
Reverse the second half.
Merge the two halves alternately.

This is the standard O(n) time and O(1) space approach.

Step 1: Find the Middle

Use slow and fast pointers.

slow = head
fast = head

Move:

slow = slow.next
fast = fast.next.next

When fast reaches the end, slow is near the middle.

For:

1 -> 2 -> 3 -> 4 -> 5

slow stops at 3.

For:

1 -> 2 -> 3 -> 4

slow stops at 2.

We will split after slow.

Step 2: Reverse the Second Half

After finding the middle:

second = slow.next
slow.next = None

This splits the list into two lists.

Then reverse second.

Example:

4 -> 5

becomes:

5 -> 4

The standard linked-list reversal uses three pointers:

prev = None
curr = second

Then repeatedly redirect:

curr.next = prev

Step 3: Merge Alternately

Now we have:

first:  1 -> 2 -> 3
second: 5 -> 4

Merge one node from first, then one node from second.

Result:

1 -> 5 -> 2 -> 4 -> 3

We only need to loop while second exists, because the first half is always at least as long as the second half.

Algorithm

If the list has zero or one node, return.
Find the middle using slow and fast pointers.
Split the list after the middle.
Reverse the second half.
Merge the first half and reversed second half alternately.

Correctness

After the middle step, the list is split into two parts. The first part contains the earlier nodes in their original order. The second part contains the later nodes in their original order.

After reversing the second part, its nodes appear from the end of the original list backward:

Ln -> Ln-1 -> Ln-2 -> ...

The merge step alternates one node from the first half and one node from the reversed second half.

Therefore, the merged list begins:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2

which is exactly the required order.

All operations only change next pointers. No node value is modified. Therefore, the algorithm produces the required in-place reordered list.

Complexity

Let n be the number of nodes.

Metric	Value	Why
Time	`O(n)`	Find middle, reverse half, and merge
Space	`O(1)`	Only pointer variables are used

Implementation

# 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:
        if head is None or head.next is None:
            return

        slow = head
        fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        prev = None
        curr = second

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        first = head
        second = prev

        while second:
            first_next = first.next
            second_next = second.next

            first.next = second
            second.next = first_next

            first = first_next
            second = second_next

Code Explanation

First, handle very short lists:

if head is None or head.next is None:
    return

A list with zero or one node already satisfies the required order.

Find the middle:

while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

After this loop, slow points to the end of the first half.

Split the list:

second = slow.next
slow.next = None

This line is important. Without it, the final list can accidentally form a cycle.

Reverse the second half:

prev = None
curr = second

while curr:
    next_node = curr.next
    curr.next = prev
    prev = curr
    curr = next_node

After reversal, prev is the head of the reversed second half.

Then merge:

first = head
second = prev

At each step, save the next pointers first:

first_next = first.next
second_next = second.next

Then connect:

first.next = second
second.next = first_next

Move both pointers forward:

first = first_next
second = second_next

The merge stops when the reversed second half is exhausted.

Testing

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

def build_list(values):
    dummy = ListNode(0)
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    result = []
    curr = head

    while curr:
        result.append(curr.val)
        curr = curr.next

    return result

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4])
    s.reorderList(head)
    assert to_list(head) == [1, 4, 2, 3]

    head = build_list([1, 2, 3, 4, 5])
    s.reorderList(head)
    assert to_list(head) == [1, 5, 2, 4, 3]

    head = build_list([1])
    s.reorderList(head)
    assert to_list(head) == [1]

    head = build_list([1, 2])
    s.reorderList(head)
    assert to_list(head) == [1, 2]

    head = build_list([1, 2, 3])
    s.reorderList(head)
    assert to_list(head) == [1, 3, 2]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[1, 2, 3, 4]`	Even-length list
`[1, 2, 3, 4, 5]`	Odd-length list
`[1]`	Single node
`[1, 2]`	Two nodes already stay valid
`[1, 2, 3]`	Small odd-length reorder