LeetCode Solutions Blog

Merge Two Sorted Lists

Number: 21

Difficulty: Easy

Paid? No

Problem Description

Given two sorted linked lists, merge them into one sorted list by splicing together the nodes from both lists. Return the head of the merged linked list.

Key Insights

Leverage the fact that both lists are sorted.
Use two pointers (one for each list) to compare nodes sequentially.
Create a dummy node to simplify edge cases and build the resulting list.
Iterate until one list is exhausted, then append the remaining nodes from the other list.
There is also a recursive approach that can simplify the logic but may use more stack space.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of the two lists. Space Complexity: O(1) for the iterative solution (O(n + m) stack space for the recursive solution).

Solution

We use an iterative approach with a dummy node to merge two sorted linked lists. Two pointers traverse list1 and list2; at each step, the node with the smaller value is appended to our merged list. This process repeats until one of the lists is exhausted, after which we append the remaining nodes from the other list. This approach works in one pass over both lists, ensuring linear time complexity and constant extra space usage.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Create a dummy node to serve as the start of the merged list
    dummy = ListNode(-1)
    current = dummy

    # Iterate while both lists have nodes
    while list1 and list2:
        # Compare the values of the current nodes of both lists
        if list1.val <= list2.val:
            current.next = list1  # Link the smaller node to the merged list
            list1 = list1.next    # Move the pointer in list1
        else:
            current.next = list2
            list2 = list2.next
        current = current.next   # Move the pointer in the merged list

    # Once one list is exhausted, attach the remaining nodes from the other list
    if list1:
        current.next = list1
    else:
        current.next = list2

    # The merged list head is at dummy.next
    return dummy.next