Example 1
ready- Input
head = [ 1, 2, 3, 4 ]- Expected
[ 1, 4, 2, 3 ]- Why
- take from the front, back, front, then back
Reorder List
35 min · reorderList()mediumOpen in LeetCode #143 ↗
Picture a row of cards. You take the front card, then the back card, then the new front, then the new back. That alternating rhythm is the order you need here.
A linked list is a chain of nodes where each node's next field links to the one
after it. Its nodes currently appear as L0 → L1 → ... → Ln-1, where L0 is the first
node and Ln-1 is the last. Rearrange them into L0 → Ln-1 → L1 → Ln-2 → ..., then
return the head of the reordered list.
A few ground rules:
- Take one node from the front, then one from the back, until every node is used.
- Keep every stored value unchanged; you're rearranging nodes, not editing their data.
- The first node remains the head.
- Odd and even lengths both follow the same front-back rhythm.
Constraints
1 <= length <= 10_000-1_000_000_000 <= Node.val <= 1_000_000_000
Hints
Write the order down
An array makes the target order easy to see: use one index at the front and another at the back, alternating between them. That's a useful baseline, even though it costs O(n) extra space.
Turn one list into two
Find the middle. If you reverse the second half, the nodes you need from the back become available from left to right.
Weave without a cycle
Cut the link at the middle before reversing. Then alternate one node from the first half and one from the reversed second half, saving both next pointers before you overwrite either one.
Follow-up
Can you rearrange the existing nodes in O(n) time and O(1) extra space, without an array or a newly built list?
Visible cases
Examples
Example 2
ready- Input
head = [ 1, 2, 3, 4, 5 ]- Expected
[ 1, 5, 2, 4, 3 ]- Why
- the middle node is used once at the end
Example 3
ready- Input
head = [ 1 ]- Expected
[ 1 ]- Why
- one node is already in the requested order
Interview signal
Asked at
AmazonMetaGoogle
Array interleave + rebuild
Copy the values into an array. Two indices now make the requested order mechanical:
take from left, take from right, then move both inward. Build a new list from that
sequence.
def reorder_list(head: ListNode | None) -> ListNode | None:
values: list[int] = []
current = head
while current is not None:
values.append(current.val)
current = current.next
ordered: list[int] = []
left, right = 0, len(values) - 1
while left <= right:
ordered.append(values[left])
if left != right:
ordered.append(values[right])
left += 1
right -= 1
dummy = ListNode()
tail = dummy
for value in ordered:
tail.next = ListNode(value)
tail = tail.next
return dummy.nextThe left != right check matters for odd lengths: when both indices meet, that middle
node belongs in the result exactly once.
Time O(n) — collect, interleave, and rebuild in linear passes. Space O(n) for the arrays and rebuilt nodes.
Split, reverse + merge
The O(1)-space version turns the front-back request into a front-front merge:
- Find the end of the first half with a slow/fast pointer pair: one pointer moves one step while the other moves two.
- Cut the list there and reverse the second half. Its old back is now at the front.
- Weave one node from each half until the reversed half is empty.
def reorder_list(head: ListNode | None) -> ListNode | None:
if head is None or head.next is None:
return head
slow = head
fast = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
reversed_head = None
while second is not None:
next_node = second.next
second.next = reversed_head
reversed_head = second
second = next_node
first = head
second = reversed_head
while second is not None:
next_first = first.next
next_second = second.next
first.next = second
second.next = next_first
first = next_first
second = next_second
return headCutting at slow keeps the merge from forming a cycle — a loop of links that never
reaches null. The first half has at least as many nodes as the second, so every node
from the reversed half always has a front-half node to follow.
Time O(n) — finding, reversing, and merging are three linear passes. Space O(1) — the existing links do all the storage work.
LeetCode's version mutates the list in place and returns void; ours returns the reordered list so the judge can compare it.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 4, 2, 3 ]
Run: visible + custom · Submit: full suite