Merge Two Sorted Lists

Difficulty: Easy Source: NeetCode

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Example 1: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2: Input: list1 = [], list2 = [] Output: []

Constraints:

• The number of nodes in both lists is in the range [0, 50]
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Traversal — walking a list node by node using .next
• Dummy Head Trick — using a sentinel node to simplify edge cases in list construction
• Two-Pointer Technique — advancing two pointers independently based on a comparison

1. Brute Force / Naive Approach

Intuition

Forget about the linked list structure for a moment. Collect all values from both lists into a Python list, sort it, then rebuild a linked list. It’s straightforward but wastes memory and ignores the fact that both inputs are already sorted.

Algorithm

1. Walk list1 and collect all values.
2. Walk list2 and collect all values.
3. Sort the combined values.
4. Build a new linked list from the sorted values and return its head.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def mergeTwoLists_brute(list1, list2):
    values = []
    cur = list1
    while cur:
        values.append(cur.val)
        cur = cur.next
    cur = list2
    while cur:
        values.append(cur.val)
        cur = cur.next

    values.sort()

    dummy = ListNode(0)
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

# Test cases
l1 = build_list([1, 2, 4])
l2 = build_list([1, 3, 4])
print("Output: ", end=""); print_list(mergeTwoLists_brute(l1, l2))  # 1->1->2->3->4->4

print("Output: ", end=""); print_list(mergeTwoLists_brute(None, None))  # None

l3 = build_list([])
l4 = build_list([0])
print("Output: ", end=""); print_list(mergeTwoLists_brute(l3, l4))  # 0

Complexity

• Time: O((m+n) log(m+n)) — sorting all values
• Space: O(m+n) — storing all values

2. Iterative with Dummy Head (Optimal)

Intuition

Since both lists are already sorted, we can merge them in one pass using the classic merge step from merge sort. We compare the heads of both lists, pick the smaller one, attach it to our result, and advance that list’s pointer. A dummy head node makes it easy to handle the “empty result” edge case — we just return dummy.next at the end.

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

Step 1: compare 1 vs 1 → pick list1's 1, result: 1
Step 2: compare 2 vs 1 → pick list2's 1, result: 1 -> 1
Step 3: compare 2 vs 3 → pick list1's 2, result: 1 -> 1 -> 2
Step 4: compare 4 vs 3 → pick list2's 3, result: 1 -> 1 -> 2 -> 3
Step 5: compare 4 vs 4 → pick list1's 4, result: 1 -> 1 -> 2 -> 3 -> 4
Step 6: list1 exhausted → append rest of list2 (just 4)
Final:  1 -> 1 -> 2 -> 3 -> 4 -> 4

Algorithm

1. Create a dummy sentinel node and set cur = dummy.
2. While both list1 and list2 are not None:
   • If list1.val <= list2.val, attach list1 and advance list1.
   • Otherwise, attach list2 and advance list2.
   • Advance cur.
3. Attach whichever list still has remaining nodes.
4. Return dummy.next.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)  # sentinel node
    cur = dummy

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

    # Attach any remaining nodes (at most one list has leftover)
    cur.next = list1 if list1 else list2

    return dummy.next

# Test cases
l1 = build_list([1, 2, 4])
l2 = build_list([1, 3, 4])
print("Output: ", end=""); print_list(mergeTwoLists(l1, l2))  # 1->1->2->3->4->4

print("Output: ", end=""); print_list(mergeTwoLists(None, None))  # None

l3 = build_list([])
l4 = build_list([0])
print("Output: ", end=""); print_list(mergeTwoLists(l3, l4))  # 0

l5 = build_list([1, 3, 5])
l6 = build_list([2, 4, 6])
print("Output: ", end=""); print_list(mergeTwoLists(l5, l6))  # 1->2->3->4->5->6

Complexity

• Time: O(m+n) — single pass through both lists
• Space: O(1) — we reuse existing nodes, only allocate the dummy node

Common Pitfalls

Not handling the case when one list is exhausted early. The while loop exits as soon as either list is empty. You need cur.next = list1 if list1 else list2 to attach what’s left — don’t try to loop again.

Forgetting the dummy node. Without a dummy, you’d need special-case logic for setting the initial head. The dummy node makes the code uniform — every node is added via cur.next.

Using <= vs < in the comparison. Using <= means when values are equal, we prefer list1. This is fine for correctness but matters if you’re asked to be stable — either way, both lists get fully consumed.