Domain 1EasyCORE

Merge Two Sorted Lists

The problem requires merging two sorted linked lists into one sorted linked list. The input consists of two pointers to the heads of the linked lists, `l1` and `l2`. The output should be a single pointer to the head of the merged linked list. The constraints are that both input lists are already sorted in non-decreasing order, and they can contain duplicate values or negative numbers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List#Recursion

21. Merge Two Sorted Lists

Model: qwen2.5-coder:14b
Topics: Linked List,Recursion
FAANG asked: 1
Acceptance rate: 56.4%


Problem Breakdown

The problem requires merging two sorted linked lists into one sorted linked list. The input consists of two pointers to the heads of the linked lists, l1 and l2. The output should be a single pointer to the head of the merged linked list. The constraints are that both input lists are already sorted in non-decreasing order, and they can contain duplicate values or negative numbers.

Intuition

A brute-force approach would involve creating a new list and iterating through both input lists simultaneously, comparing their current nodes and appending the smaller one to the new list. This method is inefficient because it requires additional space for the new list and has a time complexity of O(n + m), where n and m are the lengths of the two lists.

A more efficient approach involves using recursion or iteration to merge the lists in place, reducing both time and space complexity. The key insight is that since both input lists are already sorted, we can compare their current nodes and recursively/iteratively build the merged list by choosing the smaller node at each step.

Approach

We will use an iterative approach to merge the two linked lists. We’ll create a dummy node to serve as the starting point of the merged list and use a pointer current to keep track of the last node in the merged list. We’ll iterate through both input lists, comparing their current nodes and appending the smaller one to the merged list. If one list is exhausted before the other, we’ll append the remaining nodes of the non-exhausted list to the merged list.

Complexity Analysis

  • Time Complexity: O(n + m), where n and m are the lengths of the two input lists. We iterate through each node exactly once.
  • Space Complexity: O(1) for the iterative approach, as we only use a constant amount of extra space (for pointers). The recursive approach would have a space complexity of O(min(n, m)) due to the call stack.

Solution

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

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # Create a dummy node to serve as the starting point of the merged list
    dummy = ListNode()
    current = dummy
    
    # Iterate through both lists until one is exhausted
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Append the remaining nodes of the non-exhausted list
    if l1:
        current.next = l1
    elif l2:
        current.next = l2
    
    # Return the merged list, which starts at dummy.next
    return dummy.next

Edge Cases Handled

  • Both lists are empty: The function returns an empty list.
  • One list is empty: The function returns the non-empty list.
  • Lists with duplicate values: The function correctly merges duplicates in sorted order.
  • Lists with negative numbers: The function handles negative numbers as part of the sorting process.