Reorder List

You are given the head of a singly linked list. Reorder it such that the nodes are arranged in the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... You may not modify the values in the list's nodes; only node links 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]

Solution Approach - Find Middle, Reverse Second Half, Merge

The solution uses three steps:

Step 1 - Find the middle: Use slow/fast pointers to split the list into two halves.
Step 2 - Reverse the second half: Reverse the second half in-place so that traversing from the end becomes possible in O(1) space.
Step 3 - Merge the two halves: Interleave nodes from the first half and the reversed second half alternately.

Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class ReorderList {

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

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

        // Step 2: Reverse second half
        ListNode second = slow.next;
        slow.next = null; // cut the list
        ListNode prev = null;
        ListNode curr = second;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        second = prev; // second now points to reversed second half

        // Step 3: Interleave the two halves
        ListNode first = head;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

Complexity Analysis:

Time complexity: O(n). Each of the three steps (find middle, reverse, merge) takes O(n/2).
Space complexity: O(1) as the reordering is done in-place with a constant number of pointers.