Checkpoint Lobby Weave
Reorder each nonzero linked-list block by alternating front and back nodes
An online game's lobby queue is stored as a singly linked list. A node with value 0 is a synchronization checkpoint; every other node represents a player ticket. Ticket values may repeat and may be negative.
Each maximal consecutive block of player nodes must be rearranged independently. Within a block, take nodes alternately from the front and back of its original order: first, last, second, second-last, and so on, until every node has been taken exactly once.
Checkpoint nodes must remain between the same blocks, and consecutive checkpoints must remain consecutive. Do not move nodes across a checkpoint.
Return the head of the rearranged list. Rewire the existing nodes without changing their values or creating replacement nodes. Your algorithm must run in linear time and use constant auxiliary space; copying the list into an array does not meet these requirements.
An empty queue remains empty.
Examples
Example 1
Input: head = [12,9,4,8,0,7,3,6] Output: [12,8,9,4,0,7,6,3]
The checkpoint separates a four-player block from a three-player block. Each block independently alternates between its original frontmost and backmost remaining nodes.
Example 2
Input: head = [0,-2,5,0,0,4,0] Output: [0,-2,5,0,0,4,0]
The leading checkpoint, the pair of consecutive checkpoints, and the trailing checkpoint stay in place. The two-player block already has the required order, and the single-player block is unchanged.
Example 3
Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]
There are no checkpoints, so all five nodes form one block. The original middle node is taken last.
Constraints
- The list contains between 0 and 6000 nodes.
- -1000000 <= node.val <= 1000000.
- The input list is acyclic.
- A value of 0 always denotes a checkpoint; every nonzero value denotes a player ticket.
- Rewire existing nodes in O(n) time using O(1) auxiliary space.
Node identity matters during rewiring, even when ticket values repeat. The platform serializes the returned list as its sequence of values.
Hints
Show hint 1Hint 1
Process one checkpoint-delimited block at a time, remembering the node immediately after it.
Show hint 2Hint 2
Keep the longer half first when a block has odd length. Reverse the second half, then alternate nodes from the two halves.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the pointer operations if each block had to begin with its original last node instead?
- Can you implement the same transformation for a doubly linked list without reversing any sublist?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem