Step 1: Find middle using fast-slow pointers.
Step 2: Reverse the second half.
Step 3: Merge alternately.
# Step 1: Find middle
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = null
# Step 2: Reverse second half
second = reverse(second)
# Step 3: Merge alternately
first = head
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
Time: . Space: .