CA 15 - Merge Two Linked List

Problem Statement: here

PS Goal:
We have two sorted linked list. We need to merge them into one sorted linked list and return the head node.

Solution:

def mergeTwoLists(list1, list2):
    start = ListNode(-1)
    current = start
    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
    else:
        current.next = list2
    return start.next

• The function merges two sorted linked lists by comparing their nodes one by one and building a new sorted list using the same nodes.
• It uses a dummy node as a starting point, then repeatedly picks the smaller value from the two lists and links it to the result, moving forward in that list.
• Once one list is fully used, it attaches the remaining nodes of the other list.
• Finally, it returns start.next, which is the head of the merged sorted linked list.