Merge Two Linked List

 Let's explain the concept of merging two linked lists in Python and solve a question from LeetCode using this concept. One such problem is "Merge Two Sorted Lists" (LeetCode problem #21).

Problem Statement: Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example: Input: List 1: 1 -> 2 -> 4 List 2: 1 -> 3 -> 4 Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

To solve this problem, we can use the approach of merging two sorted arrays. We'll create a dummy node as the head of the merged list and iterate through both lists, comparing the values of the nodes and linking them accordingly.

Here's the complete code to solve the problem:


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


def merge_two_lists(l1, l2):
    # Create a dummy node as the head of the merged list
    dummy = ListNode(0)
    # Initialize a current pointer to track the merged list
    curr = dummy

    # Iterate until either of the lists becomes empty
    while l1 and l2:
        # Compare the values of the nodes in both lists
        if l1.val < l2.val:
            # Link the current pointer to the smaller value node
            curr.next = l1
            # Move the current pointer in the first list
            l1 = l1.next
        else:
            # Link the current pointer to the smaller value node
            curr.next = l2
            # Move the current pointer in the second list
            l2 = l2.next
        # Move the current pointer in the merged list
        curr = curr.next

    # Connect the remaining nodes of the non-empty list
    if l1:
        curr.next = l1
    if l2:
        curr.next = l2

    # Return the merged list (excluding the dummy head)
    return dummy.next


# Example usage
# Create two sorted linked lists
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(4)

list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)

# Merge the two lists
merged_list = merge_two_lists(list1, list2)

# Print the merged list
while merged_list:
    print(merged_list.val, end=" -> ")
    merged_list = merged_list.next
print("None")

In this code, we create two sorted linked lists: list1 with nodes [1, 2, 4] and list2 with nodes [1, 3, 4]. We then call the merge_two_lists function to merge the two lists. The resulting merged list is printed as "1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None".

Time and Space Complexity Analysis: The time complexity of this solution is O(m + n), where m and n are the lengths of the two input linked lists. We need to traverse both lists once to merge them, and the number of iterations is proportional to the total number of nodes.

The space complexity is O(1) because we are not using any extra space that grows with the input size. We only use a constant amount of space for the dummy node and the pointers.

Let's solve a question from LeetCode called "Merge k Sorted Lists" (LeetCode problem #23) using the concept of merging two linked lists.

Problem Statement: Merge k sorted linked lists and return it as one sorted list.

Example: Input: List 1: 1 -> 4 -> 5 List 2: 1 -> 3 -> 4 List 3: 2 -> 6 Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

To solve this problem, we can utilize the concept of merging two sorted lists iteratively. We'll start with the first two lists and merge them, then merge the result with the next list, and so on until we merge all the lists into a single sorted list.

Here's the complete code to solve the problem: 


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


def merge_two_lists(l1, l2):
    # Create a dummy node as the head of the merged list
    dummy = ListNode(0)
    # Initialize a current pointer to track the merged list
    curr = dummy

    # Iterate until either of the lists becomes empty
    while l1 and l2:
        # Compare the values of the nodes in both lists
        if l1.val < l2.val:
            # Link the current pointer to the smaller value node
            curr.next = l1
            # Move the current pointer in the first list
            l1 = l1.next
        else:
            # Link the current pointer to the smaller value node
            curr.next = l2
            # Move the current pointer in the second list
            l2 = l2.next
        # Move the current pointer in the merged list
        curr = curr.next

    # Connect the remaining nodes of the non-empty list
    if l1:
        curr.next = l1
    if l2:
        curr.next = l2

    # Return the merged list (excluding the dummy head)
    return dummy.next


def merge_k_lists(lists):
    # Handle edge case of an empty list
    if not lists:
        return None

    # Merge the lists iteratively
    while len(lists) > 1:
        merged = []
        # Merge adjacent pairs of lists
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two_lists(l1, l2))
        # Replace the original list with the merged list
        lists = merged

    # Return the final merged list
    return lists[0]


# Example usage
# Create three sorted linked lists
list1 = ListNode(1)
list1.next = ListNode(4)
list1.next.next = ListNode(5)

list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)

list3 = ListNode(2)
list3.next = ListNode(6)

# Merge the three lists
merged_list = merge_k_lists([list1, list2, list3])

# Print the merged list
while merged_list:
    print(merged_list.val, end=" -> ")
    merged_list = merged_list.next
print("None")

In this code, we create three sorted linked lists: list1 with nodes [1, 4, 5], list2 with nodes [1, 3, 4], and list3 with nodes [2, 6]. We then call the merge_k_lists function, passing the three lists as input. The resulting merged list is printed as "1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> None".

Time and Space Complexity Analysis: The time complexity of this solution is O(Nlogk), where N is the total number of nodes across all the lists and k is the number of lists. The merging process is done iteratively, merging two lists at a time until all the lists are merged into a single list. Since we merge pairs of lists log(k) times, and each merge takes O(N) time, the overall time complexity is O(Nlogk).

The space complexity is O(1) because we are not using any extra space that grows with the input size. We only use a constant amount of space for the dummy node, pointers, and the merged list during the merging process.

 

 

Next Post Previous Post