Weave List Halves
Problem
Given the head of a singly linked list holding at least one node, rearrange it so the nodes alternate between the front and the back: first node, last node, second node, second-to-last node, and so on. The nodes themselves must be relinked, not copied into a new list. Return the head of the rearranged list.
Examples
Input: head = 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3Input: head = 1 -> 2 -> 3
Output: 1 -> 3 -> 2
Why: an odd length leaves the middle node at the endInput: head = 7
Output: 7
Why: edge case, a single node is already in the required orderHints
0 / 3
The trouble is that a singly linked list cannot walk backwards, yet the target order keeps reaching for the last node. Consider changing the list so backwards is no longer needed.
Break the job into three familiar sub-tasks over the same nodes: locate the middle, turn the second half around, then interleave two chains.
Use a slow and a fast traveller to stop at the end of the first half, cut the list there, reverse the tail chain in place, then repeatedly take one node from each chain and link them alternately until the reversed chain is exhausted.
Solution
Three classic moves compose into the answer: find the midpoint with a slow and fast pointer, reverse the second half in place, then zip the two chains together one node at a time. Splitting at the midpoint guarantees the front chain is never shorter than the reversed back chain, so the zip ends cleanly on odd and even lengths alike. Everything happens by relinking, so no second list is built. Time is O(L) across the three passes, and space is O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def weave(head):
slow = fast = head # slow stops at the end of the first half
while fast.next and fast.next.next: slow, fast = slow.next, fast.next.next
back, slow.next = slow.next, None # cut the list in two
prev = None
while back: back.next, prev, back = prev, back, back.next # reverse the tail
front = head
while prev: # zip one node from each chain
nf, nb = front.next, prev.next
front.next, prev.next = prev, nf
front, prev = nf, nb
return head
print(dump(weave(build([1, 2, 3, 4])))) # -> [1, 4, 2, 3]
print(dump(weave(build([1, 2, 3])))) # -> [1, 3, 2]
print(dump(weave(build([7])))) # -> [7]Stuck on the idea rather than the code? Reverse a Linked List covers it.