Ski Patrol Chain Exchanges
Final linked list after segment exchanges and undo operations
A ski resort keeps its patrol assignment order as a singly linked chain. Each node contains a distinct, nonzero patrol identifier.
You receive the chain's head and a sequence of operations. Process the operations in order:
- Exchange: An operation
[a, b, c, d]identifies two inclusive segments in the current chain: the segment from identifierathrough identifierb, and the segment from identifiercthrough identifierd. The first segment occurs entirely before the second. Exchange their positions, preserving the internal order of each segment and of every node between them. - Undo: An empty operation
[]undoes the most recent exchange that has not already been undone. If there is no such exchange, it does nothing. An undone exchange is discarded; there is no redo operation.
For an exchange, the chain has the form prefix → first segment → middle → second segment → suffix. It must become prefix → second segment → middle → first segment → suffix. The middle, prefix, or suffix may be empty, and either segment may contain just one node.
Every exchange is guaranteed to name existing identifiers and valid, disjoint segments in the current chain, including the effects of previous undo operations.
Return the final head. Rearrange the original nodes by changing their links; do not change identifiers or replace the chain with newly allocated data nodes. Auxiliary lookup tables and operation history are allowed.
Examples
Example 1
Input: head = [1,2,3,4,5,6,7], operations = [[2,3,5,6],[]] Output: [1,2,3,4,5,6,7]
The first exchange moves the two-node segment beginning at identifier 2 into the position of the segment beginning at identifier 5, and vice versa. The node between those segments keeps its position between them. The following undo restores the original chain.
Example 2
Input: head = [10,20,30,40,50], operations = [[10,20,30,50]] Output: [30,40,50,10,20]
The two named segments are adjacent and together cover the entire chain. Exchanging them changes the head without reversing either segment.
Example 3
Input: head = [1,2,3,4,5], operations = [[],[1,1,4,5],[4,5,2,3],[],[4,4,1,1]] Output: [1,5,2,3,4]
The initial undo has no effect. After two exchanges, the next undo reverses only the second exchange. A new exchange then uses the current positions of its named identifiers.
Constraints
- The chain contains between 0 and 6,000 nodes.
- Every identifier is a nonzero integer between -1,000,000,000 and 1,000,000,000, inclusive.
- All identifiers in the chain are distinct.
- 0 <= operations.length <= 4,000.
- Each operation is either empty or contains exactly four identifiers.
- For every exchange, its endpoints describe two nonempty, disjoint segments, with the first segment before the second in the current chain.
- If the chain contains fewer than two nodes, all operations are undo operations.
The intended complexity is O(n + q) time and O(n + q) auxiliary space, where n is the number of nodes and q is the number of operations. A temporary sentinel node is permitted. The returned linked list is compared by its sequence of identifiers.
Hints
Show hint 1Hint 1
A singly linked node does not expose its predecessor. Can a lookup table keep that information current without visiting every node inside an exchanged segment?
Show hint 2Hint 2
Only the links at segment boundaries change. Treat adjacent segments separately, and record an inverse exchange rather than a copy of the entire chain.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you add redo operations, with a new exchange discarding the redo history?
- How would the implementation change if each node already had both next and previous links?
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