Merge Two Sorted Lists

Difficulty: Easy | Acceptance: 67.21% | Paid: No

Topics: Linked List, Recursion

• Examples
• Constraints
• Iterative Approach with Dummy Node
• Recursive Approach
• In-Place Iterative Approach

Examples

Input

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

Output

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

Input

list1 = [], list2 = []

Output

[]

Input

list1 = [], list2 = [0]

Output

[0]

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.

Iterative Approach with Dummy Node

Intuition

Create a new list by iterating through both lists, selecting the smaller node at each step and appending it to a merged list. A dummy node simplifies handling the head of the merged list.

Steps

• Use a dummy node to simplify edge cases and keep track of the head of the merged list.
• Use a current pointer to build the merged list node by node.
• Compare the values of the current nodes of both lists, and attach the smaller one to the merged list.
• Move the pointer of the chosen list forward and the current pointer of the merged list.
• Once one of the lists is exhausted, append the remaining nodes of the other list.

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

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)
    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
    elif list2:
        current.next = list2
    
    return dummy.next

Complexity

• Time: O(m + n), where m and n are the lengths of the two lists. Each node is visited at most once.
• Space: O(1). Only a constant amount of extra space is used.

Recursive Approach

Intuition

A recursive approach naturally handles the problem structure: at each step, we choose the smaller node and recursively merge the rest of the lists.

Steps

• Base cases: if one list is empty, return the other list.
• Compare the first nodes of both lists.
• Choose the smaller node as the current node of the merged list.
• Recursively merge the remainder of the chosen list with the other list.
• Return the chosen node, which becomes the head of the merged list.

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

def mergeTwoLists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    
    if list1.val <= list2.val:
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)
        return list2

Complexity

• Time: O(m + n), where m and n are the lengths of the two lists. Each node is visited at most once.
• Space: O(m + n) due to the recursion stack. In the worst case, the recursion depth is equal to the sum of the lengths of the two lists.

In-Place Iterative Approach

Intuition

We can merge the two lists without creating a dummy node by maintaining references to the head and current nodes directly from the input lists.

Steps

• Handle base cases where one of the lists is empty.
• Choose the list with the smaller first node as the primary list (head of the result).
• Iterate through the primary list, inserting nodes from the secondary list in the correct positions.
• Maintain pointers to the current node in the primary list, the previous node, and the current node in the secondary list.
• Insert nodes from the secondary list into the primary list when appropriate, and move pointers accordingly.

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

def mergeTwoLists(list1, list2):
    if not list1: return list2
    if not list2: return list1
    
    # Ensure list1 is the list with the smaller first node
    if list1.val > list2.val:
        list1, list2 = list2, list1
    
    head = list1
    
    while list1.next:
        if list2 and list2.val < list1.next.val:
            temp = list1.next
            list1.next = list2
            list2 = list2.next
            list1.next.next = temp
        list1 = list1.next
    
    if list2:
        list1.next = list2
    
    return head

Complexity

• Time: O(m + n), where m and n are the lengths of the two lists. Each node is visited at most once.
• Space: O(1). Only a constant amount of extra space is used.