Reorder List

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln-1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

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]

Approach: Find Middle, Reverse, and Merge

To solve this problem in $O(1)$ extra space, we can break it down into three distinct phases that utilize common linked list techniques.

Step 1: Find the Middle of the List
We use the Fast and Slow Pointers (Tortoise and Hare) technique. We initialize slow at head and fast at head.next. By moving fast two steps and slow one step at a time, slow will point to the middle of the list when fast reaches the end.
(Note: Starting fast at head.next ensures that slow lands on the exact node we want to split at for both even and odd length lists).

Step 2: Reverse the Second Half
Once we find the middle, the second half of the list starts at slow.next. We need to sever the connection between the first and second half by setting slow.next = null. Then, we take the second half and reverse it entirely (using the standard 3-pointer reverse technique).

Step 3: Merge the Two Halves
Now we have two separate linked lists: the first half (starting at head) and the reversed second half. We merge them by alternating nodes: taking one from the first half, then one from the second half, and so on until the second half is exhausted.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
function reorderList(head) {
    if (!head || !head.next) return;
    
    // 1. Find the middle of the list using slow & fast pointers
    let slow = head;
    let fast = head.next;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. Reverse the second half of the list
    let second = slow.next;
    slow.next = null; // Sever the link to split into two separate lists
    let prev = null;
    
    while (second !== null) {
        let nextTemp = second.next;
        second.next = prev;
        prev = second;
        second = nextTemp;
    }
    
    // 3. Merge the two halves alternately
    let first = head;
    second = prev; // 'prev' now points to the head of the reversed second half
    
    while (second !== null) {
        // Store next nodes
        let tmp1 = first.next;
        let tmp2 = second.next;
        
        // Re-wire pointers to alternate
        first.next = second;
        second.next = tmp1;
        
        // Advance pointers for the next iteration
        first = tmp1;
        second = tmp2;
    }
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the number of nodes in the linked list. We find the middle in $O(n/2)$ time, reverse the second half in $O(n/2)$ time, and merge them in $O(n/2)$ time. The overall time scales linearly.
• Space Complexity: $O(1)$. We only manipulate existing node pointers (slow, fast, prev, curr, first, second) and do not allocate any new nodes or extra memory structures.