Merge Two Sorted Lists

LeetCode 21 · View on LeetCode

Use a dummy head and compare nodes from both lists. Append the smaller node each time, then attach whatever remains.

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

def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next, l1 = l1, l1.next
        else:
            curr.next, l2 = l2, l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

def to_list(head: ListNode | None) -> list[int]:
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

def from_list(vals: list[int]) -> ListNode | None:
    dummy = ListNode()
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

if __name__ == '__main__':
    print(to_list(merge_two_lists(from_list([1, 2, 4]), from_list([1, 3, 4]))))  # [1,1,2,3,4,4]
    print(to_list(merge_two_lists(from_list([]), from_list([]))))                  # []
    print(to_list(merge_two_lists(from_list([]), from_list([0]))))                 # [0]