Sweaty Imposter

Reorder List

MediumIn-Place Reversal of LinkedListBlind 75MidOpen on LeetCodeUpdated

You're given the head of a singly linked list L0 -> L1 -> ... -> L(n-1) -> L(n). Rearrange it into L0 -> L(n) -> L1 -> L(n-1) -> L2 -> L(n-2) -> ..., alternating one node from the front with one node from the back. You may not change the values stored in the nodes, only the next links between them. Return nothing: the list starting at head must end up in the new order.

Examples

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

input
1234null
output
1423null
Highlighted nodes come from the back of the original list.

Take the first node (1), then the last (4), then the second (2), then the second to last (3).

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

Front and back alternate as 1, 5, 2, 4. That leaves 3 with no partner, so it ends the list.

Constraints

  • 1 <= number of nodes <= 5 * 10^4
  • 1 <= Node.val <= 1000

Hints

Hint 1

The answer alternates between the front of the list and the back. What would make the back half as easy to walk as the front?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Three linear passes that only change links. Find the middle with slow and fast pointers (fast moves two steps per slow step) and cut the list after slow. Reverse the second half in place so it starts at the original tail. Then weave: alternately take one node from the front half and one from the reversed back half. O(n) time, O(1) extra space.

Time

O(n)

Space

O(1)

Pitfall

Forgetting slow.next = null after finding the middle leaves the front half still pointing into the back half, which creates a cycle once you weave. Copying nodes into an array works but costs O(n) space.

Solutions

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // 1. Find the middle.
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Reverse the second half.
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 3. Weave the two halves together.
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode firstNext = first.next, secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}
Drill This