Festival Reel Run Dispatch
Reorder a linked list by repeatedly extracting longest strictly increasing runs
A film festival keeps its screening reels in a singly linked list. Each node's integer value is the reel's cue rating.
The dispatch desk builds a new list by repeatedly performing the following operation on the remaining reels:
- Divide the remaining list into maximal strictly increasing runs. A run consists of consecutive nodes whose values strictly increase from one node to the next. It is maximal if it cannot be extended on either side while remaining strictly increasing. A single node is a valid run.
- Choose the run containing the most nodes. If several runs have that length, choose the one appearing earliest in the remaining list.
- Remove that entire run and append it to the dispatch list, preserving the order of its nodes.
- Close the gap in the remaining list. The nodes on opposite sides of the removed run become adjacent, so they may now belong to one increasing run.
Continue until no reels remain. Return the head of the dispatch list, or null if the input is empty.
Reuse the original nodes by changing their next pointers. Do not create replacement list nodes or modify node values. Auxiliary data structures containing node references and bookkeeping information are allowed.
Examples
Example 1
Input: head = [1,4,2,3,8,5,6] Output: [2,3,8,1,4,5,6]
The initial runs are [1, 4], [2, 3, 8], and [5, 6]. The three-node run is dispatched first. Closing its gap joins [1, 4] and [5, 6] into a single increasing run, which is dispatched next.
Example 2
Input: head = [7,2,5,1,4] Output: [2,5,1,4,7]
The initial runs [7], [2, 5], and [1, 4] have lengths one, two, and two. The earlier two-node run is chosen first. The remaining boundary between 7 and 1 does not increase, so those reels do not join into one run.
Example 3
Input: head = [3,3,3,3] Output: [3,3,3,3]
Equal ratings never extend a strictly increasing run. Every reel is therefore a one-node run, and the earliest-run tie rule preserves their original order.
Constraints
- The input is an acyclic singly linked list with 0 to 12,000 nodes.
- -1,000,000,000 <= node.val <= 1,000,000,000.
- The returned list must contain every original node exactly once.
- Node values must remain unchanged, and replacement list nodes must not be allocated.
The intended solution takes O(n log n) time and O(n) auxiliary space. Its heap contains run records rather than individual reels. The input list may be mutated.
Hints
Show hint 1Hint 1
Keep each current maximal run as a record containing its endpoints, length, and neighboring run records. Removing one run can affect only its two neighbors.
Show hint 2Hint 2
Use a heap ordered by decreasing run length and then increasing original start position. When neighboring runs merge, insert their updated record and lazily discard obsolete heap entries.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Explain why original start positions still resolve ties correctly after arbitrary removals and merges.
- How would you adapt the bookkeeping to return the original start position and length of every dispatched run instead of the final linked list?
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