Notebook

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

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

Source

In [1]:

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

Code

In [2]:

def merge_two_lists(l1, l2):
    """Iterative approach."""
    result = current = ListNode()
    while l1 is not None and l2 is not None:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    if l1 is not None:
        current.next = l1  # Careful with this approach, in case l1 is deleted
    else:
        current.next = l2  # Careful with this approach, in case l2 is deleted

    return result.next

Follow up:

Use a recursive (iterative) approach if your first solution iterative (recursive)

Code

In [3]:

 def merge_two_lists(l1, l2):
    """Recursive approach."""
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = merge_two_lists(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists(l1, l2.next)
        return l2

In [4]:

def merge_two_lists(l1, l2):
    """Alternative recursive approach."""
    if l1 and l2:
        if l1.val > l2.val:
            l1, l2 = l2, l1
        l1.next = merge_two_lists(l1.next, l2)
    return l1 or l2