[LeetCode 21] [Easy] Merge Two Sorted Lists

Question

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

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

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

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

Solution

Instantiate a new Node with a dummy node as the head, this new Node will hold the new sorted merged list from list1 and list2.

If there are still elements that have not been visted in both the input lists, we will compare the current visited index of list1 and list2, if list1's current node value is larger than list2's current node value, we will create a new Node, and assign that node as the next pointer of mergedList, and shift the visited index of the list2. Do the same thing for list1, if the value of the current list1's node value is smaller or equal to list2's current node value.

After the conditional terminates at the while loop, we will check if there are any remaining nodes that have yet to be visited, if there are, we will simply append the remaining nodes that have yet been visited to the mergedList since they are already in the sorted order.

Code

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

# time: o(n)
# space: o(n)
def mergeTwoLists(self, list1, list2):
    """
    :type list1: Optional[ListNode]
    :type list2: Optional[ListNode]
    :rtype: Optional[ListNode]
    """
    # create a dummy node
    mergedList = ListNode()
    head = mergedList

    # if there are still nodes remaining in both the lists
    while list1 and list2:
        # if the current node in list2 is smaller than list1's current node, add list2's current node to the mergedList
        if list1.val > list2.val:
            mergedList.next = ListNode(list2.val)
            list2 = list2.next
        else:
            mergedList.next = ListNode(list1.val)
            list1 = list1.next
        # shift the tail of the mergedList
        mergedList = mergedList.next
    
    """ 
    if there are still elements left, append the remaining ones into the mergedList since its already in sorted order, and will be larger than all the elements in the current mergedList
    """
    if list1: mergedList.next = list1
    if list2: mergedList.next = list2
    
    return head.next