We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge Two Sorted Lists

Difficulty: Easy

Problem Description

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.

Key Insights

  • The two input lists are already sorted, which simplifies the merging process.
  • A new linked list can be created by comparing the nodes of both lists and adding the smaller node to the new list.
  • This problem can be solved iteratively or recursively.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of the two lists.
Space Complexity: O(1), if we are merging in-place, or O(n + m) if creating a new list.

Solution

To merge the two sorted linked lists, we can use a two-pointer approach. We initialize a dummy node to help in building the merged list. We traverse through both lists, comparing the current nodes, and link the smaller node to the merged list. We continue this process until we reach the end of one of the lists. Finally, we link the remaining nodes of the non-empty list to the merged list.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode(0)  # Create a dummy node
    current = dummy  # Pointer to build the new list
    
    while list1 and list2:  # While both lists have nodes
        if list1.val < list2.val:  # Compare values
            current.next = list1  # Link the smaller node
            list1 = list1.next  # Move the pointer in list1
        else:
            current.next = list2  # Link the smaller node
            list2 = list2.next  # Move the pointer in list2
        current = current.next  # Move the current pointer
    
    # If there are remaining nodes in either list, attach them
    current.next = list1 if list1 else list2
    
    return dummy.next  # Return the merged list starting from the next of dummy
← Back to All Questions