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

Anni HuangAnni Huang
2 min read

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.

0
Subscribe to my newsletter

Read articles from Anni Huang directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Anni Huang
Anni Huang

I’m Anni Huang, an AI researcher-in-training currently at ByteDance, specializing in LLM training operations with a coding focus. I bridge the gap between engineering execution and model performance, ensuring the quality, reliability, and timely delivery of large-scale training projects.