Reorder List

MediumLinked List Two Pointers Recursion

A fitness app stores a workout as a singly linked list of exercise IDs, ordered from the easiest exercise to the hardest: L0, L1, L2, …, Ln. To alternate effort, it reshuffles the workout so that it jumps between the two ends of the list: L0, Ln, L1, Ln-1, L2, Ln-2, …

Rearrange the nodes in place by changing only their next links; the IDs stored in the nodes must stay as they are. The function returns nothing; the tests read the list from head afterwards.

Example 1

Input: head = [10,20,30,40,50,60]
Output: [10,60,20,50,30,40]

Explanation: The easiest and hardest remaining exercises alternate until they meet in the middle with 30 and 40.

Example 2

Input: head = [7,8,9]
Output: [7,9,8]

Explanation: With an odd number of exercises, the middle one ends the workout.

Example 3

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

Explanation: With only two exercises, the first is already followed by the last, so nothing moves.

Constraints

The workout has between 1 and 50,000 exercises.
Each ID is an integer from -1000 to 1000.

💡 Hint 1

The new order interleaves the first half of the list with the second half read backwards.

💡 Hint 2

Find the middle with slow and fast pointers, then reverse the second half in place.

💡 Hint 3

Finally merge the two halves by alternating one node from each, starting with the first half.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The target order interleaves the first half with the reversed second half, and each piece is a standard linked-list move:

Find the middle with a slow pointer (one step) and a fast pointer (two steps). When fast can't advance, slow is the last node of the first half.
Cut and reverse the list after slow, so the second half now runs Ln, Ln-1, ….
Weave the halves: take one node from the first half, then one from the reversed second half, repeating until the second half is used up. The first half is equal or one longer, so its last node already ends the list.

Everything is done by relinking, with a constant number of pointers. Copying the nodes into an array and rebuilding the links also works, but costs O(n) extra space.

Time O(n)Space O(1)

function reorderList(head) {
  if (!head || !head.next) return;
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let prev = null;
  let curr = slow.next;
  slow.next = null;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  let first = head;
  let second = prev;
  while (second) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

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 = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        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;
        }
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode} head
 * @return {void} Reorder the list in place.
 */
function reorderList(head) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit