#143 Reorder List

Mediumsolve on LeetCode ↗

frequently reported atAmazon Microsoft Meta

the problem

In plain words

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

in head = [1,2,3,4]

out [1,4,2,3]

in head = [1,2,3,4,5]

out [1,5,2,4,3]

1 ≤ number of nodes ≤ 5·10⁴
1 ≤ Node.val ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFast & slow pointers In-place linked-list rewiring

The answer alternates the front half with the reversed back half. So: find the middle, reverse the second half, then weave the two lists together — three moves you already know.

solutions

From brute force to optimal

Put nodes in an ArrayList to get O(1) access to the back, then link front/back alternately.

Collect nodes.
i = 0, j = n − 1: link i → j → i+1, move inward.
Set the last node's next to null.

timeO(n)

One pass to collect, one to relink.

spaceO(n)

The node array.

javajava.util.*

1class Solution {2    public void reorderList(ListNode head) {3        List<ListNode> nodes = new ArrayList<>();4        for (ListNode p = head; p != null; p = p.next) nodes.add(p);5        int i = 0, j = nodes.size() - 1;6        while (i < j) {7            nodes.get(i).next = nodes.get(j); // front → back8            i++;9            if (i == j) break;10            nodes.get(j).next = nodes.get(i); // back → next front11            j--;12        }13        if (!nodes.isEmpty()) nodes.get(i).next = null; // the meeting node is the new tail14    }15}

Find the end of the first half, reverse the second half, merge alternately.

slow/fast with fast.next != null && fast.next.next != null → slow ends the first half.
second = reverse(slow.next); slow.next = null.
Alternate: first → second → first.next → …

timeO(n)

Three linear passes.

spaceO(1)

In-place rewiring.

javajava.util.*

1class Solution {2    public void reorderList(ListNode head) {3        if (head == null || head.next == null) return;4        // 1. find the end of the first half5        ListNode slow = head, fast = head;6        while (fast.next != null && fast.next.next != null) {7            slow = slow.next;8            fast = fast.next.next;9        }10        // 2. reverse the second half and cut the list in two11        ListNode second = reverse(slow.next);12        slow.next = null;13        // 3. weave the halves together14        ListNode first = head;15        while (second != null) {16            ListNode n1 = first.next, n2 = second.next;17            first.next = second;18            second.next = n1;19            first = n1;20            second = n2;21        }22    }23 24    private ListNode reverse(ListNode head) {25        ListNode prev = null;26        while (head != null) {27            ListNode next = head.next;28            head.next = prev;29            prev = head;30            head = next;31        }32        return prev;33    }34}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public void reorderList(ListNode head) {3        if (head == null || head.next == null) return;4        // 1. find the end of the first half5        ListNode slow = head, fast = head;6        while (fast.next != null && fast.next.next != null) {7            slow = slow.next;8            fast = fast.next.next;9        }10        // 2. reverse the second half and cut the list in two11        ListNode second = reverse(slow.next);12        slow.next = null;13        // 3. weave the halves together14        ListNode first = head;15        while (second != null) {16            ListNode n1 = first.next, n2 = second.next;17            first.next = second;18            second.next = n1;19            first = n1;20            second = n2;21        }22    }23 24    private ListNode reverse(ListNode head) {25        ListNode prev = null;26        while (head != null) {27            ListNode next = head.next;28            head.next = prev;29            prev = head;30            head = next;31        }32        return prev;33    }34}

in the room

How to say it in the interview

talk track

Name the three sub-steps before writing any code — interviewers grade the decomposition.
Say why you cut with slow.next = null: otherwise the first half still runs into the (now reversed) second half.

traps

Forgetting slow.next = null → a cycle.
Losing first.next / second.next while weaving — save both before rewiring.

what they ask next

Follow-ups

Why not a stack of the back half?

It works (push the back half, pop while weaving) but costs O(n) space. Reversing in place gives the same back-to-front order for O(1).

before you submit

Edge cases to test

One or two nodes → unchanged.
Odd length: the middle node ends up last.
Even length: the two middle nodes end up last.

practise next