Rearrange Linked List

You're given the head of a singly linked list L0 -> L1 -> ... -> Ln-1. Reorder the nodes in place so they read L0 -> Ln-1 -> L1 -> Ln-2 -> L2 -> ... — first node, then last, then second, then second-to-last, and so on, zipping inward from both ends until they meet. Think of it as repeatedly drawing from the front of a queue and then the back, alternating, the way you'd interleave a deck by taking cards off the top and the bottom. You must rewire the existing nodes; you can't allocate a fresh list.

Signature

// A node in a singly linked list.
type ListNode = { val: number; next: ListNode | null };

// Reorders the list in place and returns the (unchanged) head.
function linkedListRearrange(head: ListNode | null): ListNode | null;

The tests build a list from an array of values and read it back into an array to compare. A node is a plain object { val, next }; the last node's next is null.

Examples

// Even length: 1 2 3 4 -> 1 4 2 3
// front=1, back=4, front=2, back=3
linkedListRearrange(build([1, 2, 3, 4]));
// list is now: 1 -> 4 -> 2 -> 3

// Odd length: 1 2 3 4 5 -> 1 5 2 4 3
// front=1, back=5, front=2, back=4, middle=3 stays last
linkedListRearrange(build([1, 2, 3, 4, 5]));
// list is now: 1 -> 5 -> 2 -> 4 -> 3

Notes

• In place. Rewire the next pointers of the existing nodes. Don't build a new list and copy values across — the target solution uses O(1) extra space.
• The interleave pattern. Walk inward from both ends: the result is first, last, second, second-to-last, third, .... The two ends meet in the middle.
• Odd vs. even length. With an even count the two halves are equal. With an odd count the extra middle node ends up last in the reordered list — see the [1,2,3,4,5] -> [1,5,2,4,3] example.
• Short lists are unchanged. An empty list (null) stays null; a single node stays itself; two nodes a -> b stay a -> b. There's nothing to interleave until there are at least three nodes.
• Return the head. The original first node is still the head after reordering — return it.