MediumLinked ListTwo PointersStackRecursion

Reorder List

1 approach, code in every language

You are given the head of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln. Rearrange it in place so the nodes interleave from both ends inward: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> and so on.

You may not change any node values; the reordering must be done by adjusting the next pointers only.

Example 1

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

Output: [1,4,2,3]

Front node 1, then back node 4, then the next front node 2, then the next back node 3.

Example 2

Input: head = [1,2,3,4,5]

Output: [1,5,2,4,3]

With an odd count the middle node 3 ends up last after the alternating merge.

Constraints

The number of nodes is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

Find Middle, Reverse, Merge

Split the list at its midpoint, reverse the second half, then weave the two halves together alternately.

Loading animation…

Intuition

The target pattern alternates one node from the front with one node from the back. Reading the second half backward is exactly what a reversed second half gives us, so the problem becomes a simple alternating merge. A slow/fast pointer scan locates the midpoint in a single pass so we can cut the list cleanly into two halves. After reversing the tail portion, we zip the halves together one node at a time. Everything is done by moving pointers, so no extra list is allocated.

Algorithm walkthrough

1Use slow and fast pointers so slow stops at the end of the first half when fast reaches the end.
2Detach the second half by setting slow.next to null, keeping second = slow.next as its head.
3Reverse the second half using the standard prev/curr pointer flip.
4Set first to the original head and second to the reversed half's head.
5Repeatedly splice one node from second between consecutive nodes of first, saving each next pointer before overwriting it.
6Stop when the reversed half is exhausted; the list is now reordered in place.

Implementation

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if head is None or head.next is None:
            return
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2

Time

O(n)

Space

O(1)

Finding the middle, reversing, and merging are each linear scans using only a handful of pointers.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Fold the Signal Relay Chain is our own problem on the technique behind Reorder List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free