LeetCode 21: Merge Two Sorted Lists

Problem Restatement

We are given the heads of two sorted linked lists:

list1
list2

Both lists are sorted in non-decreasing order.

We need to merge them into one sorted linked list and return the head of the merged list.

The merged list should be made by splicing together the nodes of the original two lists. The constraints say the total number of nodes across both lists is in the range [0, 50], node values are between -100 and 100, and both input lists are sorted in non-decreasing order.

Input and Output

Item	Meaning
Input	Two linked list heads, `list1` and `list2`
Output	Head of the merged sorted linked list
Sort order	Non-decreasing
Empty lists	Either list may be empty
Node rule	Reuse nodes by changing pointers

Example function shape:

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    ...

Examples

Example 1:

list1 = [1, 2, 4]
list2 = [1, 3, 4]

Merged result:

[1, 1, 2, 3, 4, 4]

Example 2:

list1 = []
list2 = []

Merged result:

[]

Example 3:

list1 = []
list2 = [0]

Merged result:

[0]

First Thought: Copy Values Into an Array

A simple approach is:

Traverse both lists.
Put all values into an array.
Sort the array.
Build a new linked list from the sorted values.

This works, but it ignores the fact that the two input lists are already sorted.

It also creates new nodes instead of splicing the existing lists together.

class Solution:
    def mergeTwoLists(self, list1, list2):
        values = []

        while list1:
            values.append(list1.val)
            list1 = list1.next

        while list2:
            values.append(list2.val)
            list2 = list2.next

        values.sort()

        dummy = ListNode()
        current = dummy

        for value in values:
            current.next = ListNode(value)
            current = current.next

        return dummy.next

Problem With This Approach

This solution does extra work.

Metric	Value
Time	`O((m + n) log(m + n))`
Space	`O(m + n)`

The lists are already sorted, so we can merge them in linear time.

Key Insight

This is the linked-list version of the merge step from merge sort.

At each step, compare the current heads of both lists.

Choose the smaller node and attach it to the result.

Then move forward in the list that supplied that node.

For example:

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

Compare the first nodes:

1 and 1

Choose one 1.

Then compare:

2 and 1

Choose 1.

Continue until one list is empty.

At that point, attach the rest of the other list directly.

Why a Dummy Node Helps

A dummy node gives us a stable starting point for the result list.

Without a dummy node, we need special logic for the first node.

With a dummy node:

dummy -> merged nodes

we always attach to:

current.next

At the end, return:

dummy.next

which skips the fake starting node.

Visual Walkthrough

Use:

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

Start:

dummy
current = dummy

Compare 1 and 1.

Attach list1 node:

dummy -> 1
list1 now points to 2 -> 4

Compare 2 and 1.

Attach list2 node:

dummy -> 1 -> 1
list2 now points to 3 -> 4

Compare 2 and 3.

Attach 2:

dummy -> 1 -> 1 -> 2
list1 now points to 4

Compare 4 and 3.

Attach 3:

dummy -> 1 -> 1 -> 2 -> 3
list2 now points to 4

Compare 4 and 4.

Attach one 4.

Then one list becomes empty, so attach the remaining list.

Final result:

1 -> 1 -> 2 -> 3 -> 4 -> 4

Algorithm

Create a dummy node.
Set current = dummy.
While both list1 and list2 are not empty:
- compare list1.val and list2.val
- attach the smaller node to current.next
- move the chosen list forward
- move current forward
Attach whichever list remains.
Return dummy.next.

Correctness

The algorithm maintains this invariant:

The list from dummy.next to current is sorted and contains the smallest nodes already chosen from list1 and list2.

At each step, the smallest remaining node must be one of the two current heads, because both input lists are sorted.

The algorithm compares those two heads and attaches the smaller one.

So the merged prefix remains sorted, and no smaller unchosen node is skipped.

When one list becomes empty, every remaining node in the other list is already sorted and greater than or equal to the merged prefix tail. Attaching the rest preserves sorted order.

Therefore the algorithm returns a sorted linked list containing all nodes from both input lists.

Complexity

Metric	Value	Why
Time	`O(m + n)`	Each node is visited and attached once
Space	`O(1)`	Only pointer variables are used

Here:

m = length of list1
n = length of list2

Implementation

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next

Code Explanation

Create the dummy node:

dummy = ListNode()
current = dummy

current always points to the last node in the merged list.

Loop while both lists still have nodes:

while list1 and list2:

Choose the smaller current node:

if list1.val <= list2.val:
    current.next = list1
    list1 = list1.next
else:
    current.next = list2
    list2 = list2.next

Move the result pointer forward:

current = current.next

After the loop, at least one list is empty.

Attach the remaining list:

if list1:
    current.next = list1
else:
    current.next = list2

Return the real head:

return dummy.next

Testing

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

def run_tests():
    s = Solution()

    list1 = build_list([1, 2, 4])
    list2 = build_list([1, 3, 4])
    assert to_list(s.mergeTwoLists(list1, list2)) == [1, 1, 2, 3, 4, 4]

    list1 = build_list([])
    list2 = build_list([])
    assert to_list(s.mergeTwoLists(list1, list2)) == []

    list1 = build_list([])
    list2 = build_list([0])
    assert to_list(s.mergeTwoLists(list1, list2)) == [0]

    list1 = build_list([-10, -3, 5])
    list2 = build_list([-4, 0, 6])
    assert to_list(s.mergeTwoLists(list1, list2)) == [-10, -4, -3, 0, 5, 6]

    list1 = build_list([1, 1, 1])
    list2 = build_list([1, 1])
    assert to_list(s.mergeTwoLists(list1, list2)) == [1, 1, 1, 1, 1]

    print("all tests passed")

run_tests()

Test	Why
`[1, 2, 4]`, `[1, 3, 4]`	Standard example
`[]`, `[]`	Both lists empty
`[]`, `[0]`	One list empty
Negative and positive values	Checks ordering across signs
Repeated values	Confirms duplicates are preserved