LeetCode 143 Reorder List - An interesting LinkList Problem - Two Pointers (Med, Java, O(n))

LeetCode 143 Reorder List

LeetCode 143 "Reorder List" requires transforming a linked list from L₀ → L₁ → L₂ → ... → Lₙ₋₁ → Lₙ into L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → ...

The solution uses a three-step approach:

1. Find the middle using the two-pointer technique
2. Reverse the second half of the list
3. Merge the two halves alternately

Step-by-Step Breakdown

Step 1: Find Middle

• Uses slow/fast pointers where fast moves 2x speed of slow
• When fast reaches end, slow is at the middle
• The condition fast.next != null && fast.next.next != null ensures we stop at the right position for both even and odd length lists

Step 2: Reverse Second Half

• Standard iterative linked list reversal
• slow.next = null disconnects the first half
• prev becomes the new head of the reversed second half

Step 3: Merge Alternately

• Interleave nodes from first half (head) and second half (prev)
• Always connects: first → second → first.next
• Continue until second half is exhausted

Complexity Analysis

Time Complexity: O(n)

• Finding middle: O(n)
• Reversing second half: O(n/2)
• Merging: O(n/2)
• Total: O(n)

Space Complexity: O(1)

• Only uses a constant number of pointers
• No additional data structures or recursion

Complete Solution

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

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

        // Step 2: Reverse second half
        ListNode prev = null, curr = slow.next;
        slow.next = null; // disconnect first half
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Merge two halves
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;

            first.next = second;
            second.next = tmp1;

            first = tmp1;
            second = tmp2;
        }
    }
}

The solution efficiently handles the reordering in-place without requiring extra space, making it optimal for this problem.