0035 - Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head of the new sorted linked list.

The new list should be made up of nodes from list1 and list2.

Example 1: Input: list1 = [1,2,4], list2 = [1,3,5]

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

Example 2:

Input: list1 = [], list2 = [1,2]

Output: [1,2]

Example 3:

Input: list1 = [], list2 = []

Output: []

In [18]:

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

In [19]:

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

In [20]:

def createLinkedList(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head
# Helper function to print linked list
def printList(head):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

In [23]:

# Create linked lists from arrays
list1 = createLinkedList([1,2,4])
list2 = createLinkedList([1,3,5])

# Merge and print result
result = mergeTwoLists(list1, list2)
printList(result)

1 -> 1 -> 2 -> 3 -> 4 -> 5 -> None

In [ ]: