• Nodes: 1 to 50,000
• Must modify in-place.

We want to rearrange a singly linked list in-place so that it follows an alternating "outer-to-inner" pattern: first node, last node, second node, second-to-last node, and so on. However, because a linked list has no backward pointers and no direct indexing, we cannot easily read elements from the back of the list. How can we perform this intricate folding rearrangement without allocating extra memory?

The most straightforward way is to copy all node references into a flat array. Once we have a list of references, we can use two pointers moving inward from both ends to reconnect the nodes in the desired alternating order.

While this runs in linear time, storing all the node references requires O(N) extra memory, which violates the in-place constraint and is highly inefficient for large lists.

# Copy all node references
nodes = []
curr = head
while curr:
    nodes.append(curr)
    curr = curr.next

# Reconnect using two pointers
left, right = 0, len(nodes) - 1
while left < right:
    nodes[left].next = nodes[right]
    left += 1
    if left == right:
        break
    nodes[right].next = nodes[left]
    right -= 1
nodes[left].next = None # Terminate list

To fold the list in-place with O(1) extra space, we use a three-phase surgery using these pointer states:
- Halving Pointers (slow, fast): Runners moving at 1x and 2x speeds to find the exact midpoint and split the list in half.
- Reversing Pointers (prev, curr, nxt): Standard states to reverse the second half of the list so it points backward from the tail.
- Splicing Pointers (p1, p2): Parallel heads pointing to the front of the first half and the front of the reversed second half.

To prevent infinite loops, we must explicitly sever the link between the first and second halves. After finding the midpoint with slow, we save the start of the second half (slow.next) and set slow.next = None. If we forget to sever this link, the last node of the first half will still point to the second half, creating a cycle in our final spliced structure.

Once the second half is reversed, we have two independent strands: the original front half (p1) and the reversed tail half (p2). We merge them by alternating nodes: we splice a node from p2 between the current node of p1 and its original next node.

# Phase 1: Find the middle node
slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# Phase 2: Sever the halves and reverse the second half
curr = slow.next
slow.next = None # Sever the link
prev = None
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt

# Phase 3: Interweave both strands in-place
p1 = head
p2 = prev  # Head of the reversed second half

while p2:
    # Save the next destinations
    tmp1 = p1.next
    tmp2 = p2.next
    
    # Choreographed Splice
    p1.next = p2
    p2.next = tmp1
    
    # Advance pointers
    p1 = tmp1
    p2 = tmp2

The three-phase strategy handles lengths elegantly:
- Odd Lengths (e.g. [1, 2, 3]): The first half is [1, 2], and the reversed second half is [3]. During merge, 3 is spliced after 1. The result is [1, 3, 2], terminating correctly because p2 becomes null.
- Even Lengths (e.g. [1, 2, 3, 4]): The first half is [1, 2], and the reversed second half is [4, 3]. The result is [1, 4, 2, 3].