Two branches of a clinic keep waitlists as linked lists of sign-up times, each sorted from earliest to latest. Write a function that merges them into one sorted linked list and returns its head. Reuse the existing nodes rather than creating new ones. Either list may be empty.
Write merge_waitlists(a, b) in Python or mergeWaitlists(a, b) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 18 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Which node comes first?
Both lists are sorted, so the earliest remaining time is always at the front of one of them. Compare the two fronts and take the smaller.
Step 2
Build the result as you go
Keep a tail pointer to the last node of the merged list. Attach the smaller front node to tail.next, move that list forward by one, and move tail onto the node you just attached.
Step by step1 / 3
a
1
4
9
null
b
2
3
10
null
tail
d
null
Compare the fronts, 1 and 2: take 1.
Step 3
Avoid a special case for the first node
Before anything is attached, there is no tail. Start with a dummy node and let tail = dummy, so the first attach works like every other one. The answer is dummy.next.
Step 4
When one list runs out
The other list is already sorted, so attach the whole remainder in one step: tail.next = a or b.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Create a dummy node and a tail pointer. While both lists have nodes, attach the smaller front node (ties can go either way) and advance. Then attach whatever list is left. Return dummy.next.
python
1def merge_waitlists(a, b):
2 dummy = ListNode()
↑placeholder before the merged head
3 tail = dummy
4 while a and b:
5 if a.val <= b.val:
↑take the smaller front
6 tail.next, a = a, a.next
7 else:
8 tail.next, b = b, b.next
9 tail = tail.next
↑tail = last node added
10 tail.next = a or b # the rest is already sorted
↑the leftovers are already sorted
11 return dummy.next
javascript
1function mergeWaitlists(a, b) {
2 const dummy = new ListNode()
↑placeholder before the merged head
3 let tail = dummy
4 while (a && b) {
5 if (a.val <= b.val) {
↑take the smaller front
6 tail.next = a
7 a = a.next
8 } else {
9 tail.next = b
10 b = b.next
11 }
12 tail = tail.next
↑tail = last node added
13 }
14 tail.next = a || b // the rest is already sorted
↑the leftovers are already sorted
15 return dummy.next
16}
Complexity
TimeO(n + m)SpaceO(1)
O(n + m) time, where n and m are the lengths of the lists: each node is attached once. O(1) extra space, because existing nodes are reused.
What we learned
The dummy head removes the "is this the first node?" special case.
When one input runs out, the rest of the other is already in order: attach it in one step.
This merge is the core of merge sort, so it's worth knowing by heart.