Bakery Tray Pair Checks
Reorder original adjacent pairs in a linked list smaller-value first
A bakery's inspection queue is stored as a singly linked list. Each node represents a tray, and its integer value is the tray's temperature offset from the desired temperature. Negative offsets are allowed.
The inspector processes trays in pairs formed from their original positions: positions 1 and 2, then positions 3 and 4, and so on. Within each pair, place the tray with the smaller offset first. If the offsets are equal, keep their original order. If the queue has an unpaired final tray, leave it at the end.
Return the head of the resulting linked list. Reorder the existing nodes by changing their links; do not change their values or create replacement tray nodes. You may use a temporary sentinel node.
This is not a global sort: trays must remain within their original pairs.
Examples
Example 1
Input: head = [7,2,5,1,4] Output: [2,7,1,5,4]
The original pairs are (7, 2) and (5, 1). Each pair changes order, while the unpaired tray with offset 4 stays at the end.
Example 2
Input: head = [-3,-3,8,-1] Output: [-3,-3,-1,8]
The pair (-3, -3) keeps its original order because its offsets are equal. The pair (8, -1) changes order.
Example 3
Input: head = [6] Output: [6]
A queue containing only one tray has no complete pair, so it remains unchanged.
Constraints
- The list contains between 0 and 6000 nodes.
- Each node value is an integer between -1000 and 1000, inclusive.
- The input list is acyclic.
- Reorder existing nodes without modifying their values or allocating replacement tray nodes.
The linked list is supplied and returned as a plain JSON list by the platform. The intended solution takes O(n) time and O(1) auxiliary space.
Hints
Show hint 1Hint 1
Keep a pointer to the node immediately before the pair being processed. A temporary sentinel makes the first pair behave like every other pair.
Show hint 2Hint 2
After processing a pair, advance to its final node. The next pair begins immediately after that node.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you perform the rearrangement in one pass using constant auxiliary space?
- How would the pointer updates change if every complete pair had to be reversed, regardless of its values?
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