One Van, Two Routes
Two couriers deliver along the same long street. Each one's stops are stored as a chain: every stop points to the next one, and each chain is already sorted by the stop's position along the street, in metres from the depot.
One courier calls in sick, so a single van must do both rounds in one drive down the street. The dispatcher needs one chain with every stop from both routes, still sorted by distance.
Your task
Write mergeRoutes(first, second). Both arguments are sorted linked lists (smallest distance first; null / None means no stops). Return the head of one sorted list that contains every node of both.
If both routes have a stop at the same distance, keep both stops. Reuse the existing nodes by relinking them rather than creating new ones.
mergeRoutes(first: ListNode, second: ListNode) → ListNode
Examples
first = [2, 5, 9] second = [3, 5, 12]
[2, 3, 5, 5, 9, 12]
Compare the first stops: 2 beats 3, so 2 goes first. Then 3 beats 5, then the two 5s (both kept), then 9 beats 12, and finally the 12 that is left over.
first = [] second = [7, 8]
[7, 8]
The first courier had no stops, so the van just follows the second route.
Constraints
- 0 ≤ stops in each route ≤ 5,000
- -100,000 ≤ distance ≤ 100,000 (negative means west of the depot)
- Each route is sorted in non-decreasing order.
Start with brute force
Copy every distance from both chains into an array, sort it, and build a new chain from it.
The sort costs O((n + m) log(n + m)) and throws away the fact that both routes were already sorted. It also allocates a whole new chain. Merging walks each route once, O(n + m), and reuses the nodes you already have.
Hints
0 of 4 shown- Hint 1
Look only at the first stop of each route. Which of the two must be the very first stop of the merged route?
- Hint 2
The smaller of the two front stops goes first. Take it off its route. Now you have the same question again with one stop fewer.
- Hint 3
Keep a
tailpointer to the last stop of the merged route so you can attach the next one in O(1). A dummy starting node saves you from treating the first attachment as a special case. - Hint 4
Create a dummy node and set
tail = dummy. While both routes have stops, attach the smaller front node totail.next, advance that route and advancetail. When one route runs out, attach the rest of the other in one step. Returndummy.next.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The first stop of the merged route must be the smaller of the two front stops. After you take it, the same reasoning applies to what is left. So you repeatedly compare two fronts and move the smaller one to the end of the result.
Trace 2 → 5 → 9 and 3 → 5 → 12:
- Fronts 2 and 3. Attach 2. Result: dummy → 2.
- Fronts 5 and 3. Attach 3. Result: … → 2 → 3.
- Fronts 5 and 5. Equal, take the first route's 5. Result: … → 3 → 5.
- Fronts 9 and 5. Attach 5. Result: … → 5 → 5.
- Fronts 9 and 12. Attach 9. The first route is now empty.
- Attach what is left of the second route,
12, in one step. Returndummy.next:2 → 3 → 5 → 5 → 9 → 12.
The dummy node means you never need an if for "is the result still empty?". Without it, the first attachment needs special code, and that is where bugs hide.
function mergeRoutes(first, second) {
const dummy = new ListNode(0, null); // placeholder before the real head
let tail = dummy;
while (first !== null && second !== null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first !== null ? first : second; // the leftover is already sorted
return dummy.next;
}def merge_routes(first, second):
dummy = ListNode(0) # placeholder before the real head
tail = dummy
while first is not None and second is not None:
if first.val <= second.val:
tail.next = first
first = first.next
else:
tail.next = second
second = second.next
tail = tail.next
tail.next = first if first is not None else second # leftover is sorted
return dummy.nextRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.