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.

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Example 1:

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

Example 2:

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

Example 3:

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

Solution

Approach:

To merge two sorted linked lists, we can use a dummy head node to simplify the process of building the new list without worrying about the initial null checks. We'll then use a pointer to track the current tail of our merged list and append nodes from list1 or list2 as appropriate.

  1. Initialize a dummy node: Create a dummy node (e.g., with value 0) and a current pointer pointing to this dummy node. This dummy node will serve as a placeholder for the head of the new merged list.
  2. Iterate and compare: While both list1 and list2 are not None:
    • Compare the val of the current nodes in list1 and list2.
    • Append the node with the smaller value to current.next.
    • Advance the current pointer to the newly added node.
    • Advance the pointer of the list from which the node was taken.
  3. Append remaining nodes: After the loop, one of the lists (or both) might have remaining nodes. Since these lists are already sorted, we can simply append the rest of the non-empty list to current.next.
  4. Return result: The head of the merged list will be dummy.next.

Python Code Solution:

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

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Create a dummy node to serve as the head of the merged list
    dummy = ListNode()
    current = dummy

    # Iterate while both lists have nodes
    while list1 is not None and list2 is not None:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Append any remaining nodes from list1 or list2
    if list1 is not None:
        current.next = list1
    elif list2 is not None:
        current.next = list2
            
    # The merged list starts from dummy.next
    return dummy.next