Command Palette

Search for a command to run...

Hectal
Problem 8.8 · Linked ListsMedium

Reorder List

PatternIn-Place Linked List ReversalFast and Slow PointersDummy Head and Merging

What it teaches: Three steps you already know, chained: split at the middle, reverse the second half, weave the halves together.

Practise it on judges as “Reorder List”.

The problem

Reorder L0 → L1 → … → Ln−1 → Ln into L0 → Ln → L1 → Ln−1 → L2 → … in place. Only links may change, not values.

Example 1

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

Example 2

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

Constraints

  • 1 ≤ nodes ≤ 5 × 10⁴

Pattern clues in the wording

  • → Alternate from the front and the back
  • → In place, singly linked

These clues point to In-Place Linked List Reversal: Walk the list with prev, curr and next, turning each arrow around as you go.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public void reorderList(ListNode head) {
        // 1) find the middle  2) reverse the second half  3) weave
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
head = [1,2,3,4]
[1,4,2,3]
2
head = [1,2,3,4,5]
[1,5,2,4,3]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: split, reverse, weave · O(n)
1

Optimal: split, reverse, weave

Time O(n) Space O(1)

Find the end of the first half (first middle). Cut there and reverse the second half. Then alternate: take one node from the first half, one from the reversed second half, until the second half runs out.

▶ Dry run: Weaving two halveshead = [1, 2, 3, 4, 5]
1
2
3
4
5
null

Step 1/3Split after the middle: first half 1 → 2 → 3, second half 4 → 5.

Approach 1
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {   // slow ends at the first middle
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;                                       // cut
        ListNode prev = null;                                   // reverse the second half
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }
        ListNode a = head, b = prev;                            // weave
        while (b != null) {
            ListNode an = a.next, bn = b.next;
            a.next = b;
            b.next = an;
            a = an;
            b = bn;
        }
    }
}

Verdict: Three linear passes, no extra memory.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One or two nodes
  • Odd and even lengths

Mistakes people make

  • Forgetting to cut the first half, creating a cycle.
  • Using the second middle for the split, which puts one node too many in the second half.

Interview

Follow-up questions

Could you use extra memory to make it simpler?