Easy

Merge Two Sorted Lists

LAB

Given two sorted linked lists encoded as arrays, merge them into one sorted linked list and return its values.

EXAMPLES

Example 1

Input
{
  "list1": [
    1,
    2,
    4
  ],
  "list2": [
    1,
    3,
    4
  ]
}

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

FUNCTION SHAPE

list1: intArraylist2: intArray→intArray

SOLUTION NOTE

The dummy node pattern shines here because it lets us avoid checking for edge cases like empty lists. We simply connect nodes in sorted order and return the result starting from dummy.next. This is exactly the same as merging two arrays into 1 sorted list, but just operating on a linked list data structure.

Reveal reference solution +

pythonREFERENCE

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # Iterative solution using dummy node pattern
    # Create a dummy node
    dummy = ListNode(0)
    current = dummy

    # Compare nodes from both lists and link the smaller one
    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

    # Link the remaining nodes (if any)
    current.next = l1 if l1 else l2

    # Return the merged list (excluding the dummy node)
    return dummy.next

# Recursive solution
def mergeTwoListsRecursive(self, l1: ListNode, l2: ListNode) -> ListNode:
    # Base cases
    if not l1:
        return l2
    if not l2:
        return l1

    # Recursive case: determine which node should come first
    if l1.val <= l2.val:
        # l1 comes first, so l1.next should be merged with l2
        l1.next = self.mergeTwoListsRecursive(l1.next, l2)
        return l1
    else:
        # l2 comes first, so l2.next should be merged with l1
        l2.next = self.mergeTwoListsRecursive(l1, l2.next)
        return l2

TimeO(n + m)

SpaceO(1) iterative, O(n + m) recursive

Open on LeetCode ↗