Change
1, 2, 3, 4, 5into1, 5, 2, 4, 3.
Start with the concrete trace below. It shows the state the algorithm must carry as it runs.
Problem trace
Reorder List: Find the first-half tail, reverse the detached second half, then splice one reversed node after each first-half node.
Input and goalChange `1, 2, 3, 4, 5` into `1, 5, 2, 4, 3`.
Initialize middle pointersFor 1->2->3->4->5, set slow = 1 and fast = 1. Both fast.next and fast.next.next exist.
1slow / fast→2→3→4→5
Advance middle pointers onceMove slow one link 1->2 and fast two links 1->2->3. The loop guard still passes at fast = 3.
1→2slow→3fast→4→5
Advance middle pointers twiceMove slow 2->3 and fast 3->4->5. At fast = 5, fast.next is null, so the middle loop stops.
1→2→3slow→4→5fast
Detach the second halfSave second = slow.next = 4, then write slow.next = null. The independent halves are 1->2->3 and 4->5.
4second→5
Reverse second-half node 4With previous = null and second = 4, save next_node = 5, write 4.next = null, then advance previous = 4 and second = 5.
4previous
second5
Reverse second-half node 5Save next_node = null, write 5.next = 4, then advance previous = 5 and second = null. The reversed half is 5->4.
5previous→4
Initialize the mergeSet first = head = 1 and second = previous = 5. The two independent chains are 1->2->3 and 5->4.
5second→4
Splice node 5 after node 1Save first_next = 2 and second_next = 4. Write 1.next = 5 and 5.next = 2, then advance first = 2 and second = 4.
1→5→2first→3
second4
Splice node 4 after node 2Save first_next = 3 and second_next = null. Write 2.next = 4 and 4.next = 3, then second becomes null.
1→5→2→4→3first
Finish when the second half is emptyThe merge guard fails at second = null. The in-place list is 1->5->2->4->3->null.
1→5→2→4→3
- Recognize it
- Use it when nodes must alternate from the front and back of a singly linked list without an auxiliary array or stack.
- Keep true
- The midpoint scan keeps fast twice as far along; reversal preserves a reversed prefix plus untouched suffix; merging preserves the final alternating prefix and two unconsumed chains.
- Reuse it
- Complex list transforms become safe compositions of small invariants: locate a boundary, detach, reverse with a saved route, then splice only after saving both continuations.
Pattern: Find middle, reverse second half, then merge.
Simple idea: This problem combines three linked-list moves. Slow and fast pointers find the middle. Reverse the second half. Alternate nodes from the two halves.
def reorder_list(head: ListNode | None) -> None:
if head is None or head.next is None:
return
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
previous = None
while second:
next_node = second.next
second.next = previous
previous = second
second = next_node
first = head
second = previous
while second:
first_next = first.next
second_next = second.next
first.next = second
second.next = first_next
first = first_next
second = second_nextCost: time and space.
The platform supplies ListNode with val and next; this snippet assumes that definition.