Probe Packet Fast Lane
Reorder a linked list with values at least a cutoff first, keeping group order
A deep-space probe stores outgoing telemetry packets in a singly linked list. Each node's integer value is the packet's urgency score.
Before transmission, packets with scores at least cutoff must be placed before packets with scores below cutoff. Within each of these two groups, packets must keep their original relative order.
Given the list head head and the integer cutoff, rearrange the list and return its new head. Reuse the existing nodes by changing their next pointers; do not change node values or create replacement nodes. If the list is empty, return null.
For example, the relative order of two packets that both meet the cutoff must remain unchanged, even if their scores differ.
Examples
Example 1
Input: head = [2,7,5,1,9], cutoff = 5 Output: [7,5,9,2,1]
With cutoff 5, the packets scored 7, 5, and 9 form the first group in their original order. The packets scored 2 and 1 follow, also in their original order.
Example 2
Input: head = [-3,0,-1,0], cutoff = 0 Output: [0,0,-3,-1]
With cutoff 0, both packets scored 0 go first. The packets scored -3 and -1 follow in their original order.
Example 3
Input: head = [4,2,8], cutoff = 10 Output: [4,2,8]
No packet meets cutoff 10, so the entire list keeps its original order.
Constraints
- The list contains between 0 and 4,000 nodes.
- -1,000,000 <= Node.val <= 1,000,000.
- -1,000,000 <= cutoff <= 1,000,000.
- The input list is singly linked and contains no cycle.
The platform passes head as a linked list and serializes the returned linked list as an array of values. The required order is unique. The intended solution uses O(n) time and O(1) auxiliary space.
Hints
Show hint 1Hint 1
Maintain a separate head and tail for each of the two groups.
Show hint 2Hint 2
Save a node's original successor before detaching it. Append the node to its group's tail, then connect the two completed groups.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you explain why the rearrangement takes O(n) time and O(1) auxiliary space?
- How would you generalize the approach to several priority groups while preserving the order within every group?
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