Example 1
ready- Input
l1 = [ 1, 2, 4 ] l2 = [ 1, 3, 4 ]- Expected
[ 1, 1, 2, 3, 4, 4 ]- Why
- take the smaller front value until both lists are exhausted
Merge Two Sorted Lists
25 min · mergeTwoLists()Two queues of scores are already ordered. Your job isn't to sort them again — it's to weave them into one ordered queue.
A singly linked list is a chain of nodes where each node links only to the next one.
You're given the heads of two such lists, l1 and l2. Both use non-decreasing
order, which means each value is at least as large as the value before it. Merge every
node into one non-decreasing list and return its head.
A few ground rules:
- Keep every value from both inputs, including duplicates.
- Either input may be empty; if both are empty, return an empty list.
- The result must be sorted from its first node to its last.
Constraints
0 <= l1 length, l2 length <= 10_000- Both input lists are sorted in non-decreasing order.
-1_000_000_000 <= Node.val <= 1_000_000_000
Hints
Look only at the front
The smallest unused value must be at the head of one of the two remaining lists. Compare those two nodes; nothing deeper can win yet.
Build one shared tail
Keep a tail for the merged list. Attach the smaller front node, move that input
forward, then advance tail.
One list will finish first
Once either input becomes null, the other input is already sorted. Attach that
entire remainder in one step instead of copying it node by node.
Follow-up
Can you merge by reconnecting the existing nodes, using only O(1) extra space beyond the returned list?
Visible cases
Examples
Example 2
ready- Input
l1 = [] l2 = []- Expected
[]- Why
- two empty inputs produce an empty result
Example 3
ready- Input
l1 = [] l2 = [ 0 ]- Expected
[ 0 ]- Why
- when one side is empty, the other side is already the answer
Interview signal
Asked at
AmazonMicrosoftApple
Collect + sort
Linked-list pointers can feel awkward, so the direct approach escapes to an array. Read every value from both lists, sort the combined collection, then build a fresh list.
def merge_two_lists(
l1: ListNode | None,
l2: ListNode | None,
) -> ListNode | None:
values: list[int] = []
current = l1
while current is not None:
values.append(current.val)
current = current.next
current = l2
while current is not None:
values.append(current.val)
current = current.next
values.sort()
dummy = ListNode()
tail = dummy
for value in values:
tail.next = ListNode(value)
tail = tail.next
return dummy.nextThis is correct, but it throws away the strongest fact in the input: both lists were already sorted.
Time O((m + n) log(m + n)) for the sort. Space O(m + n) for the collected values and the newly allocated nodes.
Splice merge
Splicing means reconnecting existing nodes instead of copying their values. Compare
the two current heads, splice the smaller one after tail, and advance only the list
that supplied it.
A dummy node is a temporary starter node that removes the special case for an empty
result. Its value never enters the answer; dummy.next is the real head.
def merge_two_lists(
l1: ListNode | None,
l2: ListNode | None,
) -> ListNode | None:
dummy = ListNode()
tail = dummy
left, right = l1, l2
while left is not None and right is not None:
if left.val <= right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
tail = tail.next
tail.next = left if left is not None else right
return dummy.nextThe choice is safe because every node behind left is at least left.val, and the same
is true on the right. The smaller front value is therefore the smallest value still
available anywhere.
Time O(m + n) — each node is attached once. Space O(1) — one dummy node and a few references; the result reuses the input nodes.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 1, 2, 3, 4, 4 ]
Run: visible + custom · Submit: full suite