Merge two sorted (ascending) linked lists into one sorted list, and return its head. Reuse the existing nodes.
mergeLists(a, b)
Input format: listA | listB — each already sorted ascending. Output the
merged list, space-separated.
(1 → 3 → 5) , (2 → 4 → 6) // → 1 → 2 → 3 → 4 → 5 → 6
(1 → 2) , (3 → 4) // → 1 → 2 → 3 → 4
(empty) , (1 → 2) // → 1 → 2
This looks similar to zippering two lists, but the rule for picking the next node differs: instead of blindly alternating, you pick whichever list currently has the smaller front value. Doing this correctly is what makes the result come out fully sorted.
Both lists are already sorted ascending, so the smallest remaining value in either one always sits right at its front — everything after the front is equal or larger. That means the smallest value not yet placed in the output must be one of the two front values you're looking at right now. A single comparison between the two fronts is always enough to know which one belongs next.
Use the same dummy-head-and-tail scaffolding as any "build a new list by appending" problem. Then:
Once one list is exhausted, everything already placed in the result is less than or equal to everything remaining in the other list — because you always chose the smaller front at each step. So there's no need to keep comparing one at a time; splice the entire remaining chunk of the non-empty list directly onto the tail, and the result stays sorted.
Each node from either list is visited and relinked exactly once, so total work is proportional to their combined length — you can't merge two sorted sequences faster than looking at every element once. And since you reuse the original nodes, no extra memory is needed beyond a handful of pointers.
Zipper alternates sources unconditionally; this problem picks a source based on comparison. That's the key difference, even though the surrounding dummy-head/tail machinery is identical.
def merge_lists(a, b):
dummy = ListNode(0)
tail = dummy
while a is not None and b is not None:
if a.val <= b.val:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a is not None else b
return dummy.next
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.