Reorder List — Solution in Python, Java & C++
Reorder List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers and stack.
Reorder List is a medium coding problem on two pointers, stack and recursion, asked in Amazon, Microsoft, Adobe and Meta interviews.
- Difficulty: Medium
- Topics: Two Pointers, Stack, Recursion
- Asked at: Amazon, Microsoft, Adobe, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln. Reorder it in place to
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
alternating between the front and the back of the list. Only the links may change, not the values. LeetCode's version returns nothing; here, return the head of the reordered list (it is still L0).
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]
Explanation: The middle node 3 ends up last.
Example 3
Input: head = [7]
Output: [7]
Constraints
The number of nodes in the list is in the range [1, 5 * 10^4]1 <= Node.val <= 1000
Hints for Reorder List
Hint 1
The result interleaves the first half of the list with the second half read backwards.
Hint 2
Find the middle with slow and fast pointers, then reverse the second half in place.
Hint 3
Cut the list after the middle, then merge the two halves by alternately taking one node from each.
How to solve Reorder List
Split, reverse, weave. The front half is read forwards and the back half backwards, so reversing the back half turns the problem into merging two lists by alternation.
Approach
- Find the middle:
slow = fast = head; whilefast.nextandfast.next.nextexist, moveslowone step andfasttwo. - Reverse the list after
slowto getsecond, and cut withslow.next = null. - Weave: with
first = head, whilesecondis not null, save bothnextpointers, linkfirst.next = secondandsecond.next = savedFirstNext, then advance both. - Return
head.
Why it works
The slow pointer stops at the last node of the first half (which has the extra node when the length is odd). After reversing, second lists Ln, Ln-1, … and the weave places each of them right after L0, L1, … in turn, which is exactly the required order; the first half is never shorter, so it absorbs every node of the second.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting to cut the first half (
slow.next = null) leaves a cycle. - Pushing all nodes onto a stack also works but costs O(n) extra space.
- For one or two nodes nothing changes — make sure the loops handle that without special cases.
Reference solution
Python
from typing import Optional
def reorderList(head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second, prev = slow.next, None
slow.next = None
while second:
second.next, prev, second = prev, second, second.next
first, second = head, prev
while second:
a, b = first.next, second.next
first.next = second
second.next = a
first, second = a, b
return headJava
public static ListNode reorderList(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
ListNode cur = slow.next, prev = null;
slow.next = null;
while (cur != null) { ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
ListNode first = head, second = prev;
while (second != null) {
ListNode a = first.next, b = second.next;
first.next = second;
second.next = a;
first = a;
second = b;
}
return head;
}C++
ListNode* reorderList(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
ListNode *cur = slow->next, *prev = nullptr;
slow->next = nullptr;
while (cur) { ListNode* nx = cur->next; cur->next = prev; prev = cur; cur = nx; }
ListNode *first = head, *second = prev;
while (second) {
ListNode *a = first->next, *b = second->next;
first->next = second;
second->next = a;
first = a;
second = b;
}
return head;
}JavaScript
var reorderList = function(head) {
var slow = head, fast = head;
while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; }
var cur = slow.next, prev = null;
slow.next = null;
while (cur !== null) { var nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
var first = head, second = prev;
while (second !== null) {
var a = first.next, b = second.next;
first.next = second;
second.next = a;
first = a;
second = b;
}
return head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique · Stack Data Structure