Leetcode 21: Merge Two Sorted Lists

Problem Statement

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

Merge the two lists in a 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.

Example 1:

"""
    1-->2-->4-->5
            ^list1

    1-->3-->4
                ^list2

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

                    ^curr
"""
Input: list1 = [1,2,4,5], list2 = [1,3,4]
Output: [1,1,2,3,4,4,5]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Solution

Intuition & Patterns

In order to keep track of the head of the merged list, we will create a dummy node which will function as a pre-head node. Once we have completed the merge operation, we will return dummy.next to return the actual head of the merged linked lists.

Since we need to save the memory address of the dummy variable, we will create a curr node that we can use to modify the next pointers along the path. While list1 and list2 nodes exist, we traverse through the linked lists and set the next pointer to the next smallest node. Once one of the nodes becomes None, we set curr.next to the remaining list. Returning dummy.next gives us the head of the merged list.

Python Code

# 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]:
        """
            T: O(N + M)
            SL O(1)
        """
        dummy = ListNode(-1)
        curr = dummy

        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        
        if list1:
            curr.next = list1
        else:
            curr.next = list2
        
        return dummy.next

Leetcode 21: Merge Two Sorted Lists