Description
Rearrange a list in place into first, last, second, second-last order. Do not change node values.
Solution
def reorder_list(head):
if not head or not head.next:
return
slow = fast = head
while fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
current, slow.next = slow.next, None
previous = None
while current:
following = current.next
current.next = previous
previous, current = current, following
first, second = head, previous
while second:
a, b = first.next, second.next
first.next, second.next = second, a
first, second = a, bExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,2,3,4]]- Output
[1,4,2,3]
Alternating from the ends gives 1, 4, 2, 3.
Example 2
- Input
[[1,2,3,4,5]]- Output
[1,5,2,4,3]
The middle node is appended once at the end.
Example 3
- Input
[[1]]- Output
[1]
One node is already ordered.
Approach
Split at the midpoint, reverse the second half, then weave the two halves together.
Time & space
O(n) time; O(1) space. Here n is the input length.