Core Insight Before changing a link, save the only pointer that would otherwise be lost.
Common Pitfall Always store next before redirecting current.next.
Description
Reorder linked list by interleaving from start and end.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(1)
Tags
linked-listtwo-pointersrecursion
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize the pointers.
- Save the next node.
- Rewire the current node.
- Advance both pointers until the list is consumed.
def reorderList(head):
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
prev = slow.next = None
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2