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

Table of contents

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:
- Find the middle using the two-pointer technique
- Reverse the second half of the list
- 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 halfprev
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.
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.