Calibration Review Chain
Order linked list nodes by distance to a target, keeping ties in input order
A weather station stores temperature readings in a singly linked list. Each node's integer value is a temperature reading, and the current list order is the order in which the readings arrived.
Before a calibration review, the station wants readings closest to a target temperature examined first.
Given the head of the list, head, and the target temperature, target, rearrange the nodes into nondecreasing order of abs(node.val - target).
When two readings have the same distance from target, preserve their original relative order. This applies even when their temperature values differ.
Return the head of the rearranged list. An empty list remains empty.
Rearrange the existing nodes by changing their links; do not change their values or replace them with newly created reading nodes. Your solution should run in O(n log n) time and use O(1) auxiliary space, excluding a constant number of helper nodes.
Examples
Example 1
Input: head = [3,-1,5,1,-3], target = 1 Output: [1,3,-1,5,-3]
The reading equal to the target is reviewed first. The readings 3 and -1 have equal distance from the target, so 3 must remain before -1. Likewise, 5 must remain before -3.
Example 2
Input: head = [-6,-2,-4,0,2], target = -3 Output: [-2,-4,-6,0,2]
The readings -2 and -4 tie for the smallest distance and retain their arrival order. The readings -6 and 0 also tie and retain their arrival order.
Constraints
- The list contains between 0 and 15,000 nodes.
- -1,000 <= node.val <= 1,000
- -1,000 <= target <= 1,000
The reference solutions use stable bottom-up linked-list merge sort: O(n log n) time and O(1) auxiliary space. ListNode is predefined by the platform. Stability refers to the original order of nodes, not to the numeric order of their values.
Hints
Show hint 1Hint 1
Two already ordered chains can be merged by changing next pointers. When their front nodes have equal priority, choose the node from the earlier chain.
Show hint 2Hint 2
Start with chains of length one, then merge adjacent chains in passes with lengths 1, 2, 4, and so on. This avoids a recursive call stack.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would your implementation change if O(n) auxiliary space were allowed?
- Can you adapt the merging process to take advantage of long portions of the list that are already in the required order?
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