#21. Merge Two Sorted Lists | LeetCode Python Solution

Problem

LeetCode Problem

21. Merge Two Sorted Lists

Python Solution

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        """ Excalidraw
        https://excalidraw.com/#json=0Njj8fi7qdgqwlJaNE611,67aza6gGSQFbyGNeLTw-Vg
        """

        # Create a dummy 'head' node to hold merged list and make 'curr' point to it
        head = ListNode()
        curr = head

        # Merge nodes until both lists are empty
        while list1 is not None or list2 is not None:
            # When list1 is empty
            if list1 is None:
                curr.next = list2
                curr = list2
                list2 = list2.next
            # When list2 is empty
            elif list2 is None:
                curr.next = list1
                curr = list1
                list1 = list1.next
            # When both list1 are list2 are not empty
            # Current list1 node's value is less than or equal to current list2 node's value
            elif list1.val <= list2.val:
                curr.next = list1
                curr = list1
                list1 = list1.next
            # When both list1 are list2 are not empty
            # Current list1 node's value is greater than current list2 node's value
            else:
                curr.next = list2
                curr = list2
                list2 = list2.next

        # Return the merged list by skipping the dummy node
        return head.next