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:




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]


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 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 to the remaining list. Returning gives us the head of the merged list.

leetcode 21 merge two sorted linked lists diagram

Python Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
# = 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:
       = list1
                list1 =
       = list2
                list2 =
            curr =
        if list1:
   = list1
   = list2

Leetcode 21: Merge Two Sorted Lists