Lecture 199:-  Let's Code to Concatenate and Merge Linked Lists

To merge two linked lists in a sorted order, you need to compare the nodes of both lists and rearrange them to form a single sorted linked list. Here's how you can do it in Python:

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node        else:            current_node = self.head            while current_node.next:                current_node = current_node.next            current_node.next = new_node    def display(self):        current_node = self.head        while current_node:            print(current_node.data, end=" -> ")            current_node = current_node.next        print("None") def merge_sorted_lists(list1, list2):    merged_list = LinkedList()    current_node1 = list1.head    current_node2 = list2.head    while current_node1 and current_node2:        if current_node1.data <= current_node2.data:            merged_list.append(current_node1.data)            current_node1 = current_node1.next        else:            merged_list.append(current_node2.data)            current_node2 = current_node2.next    while current_node1:        merged_list.append(current_node1.data)        current_node1 = current_node1.next    while current_node2:        merged_list.append(current_node2.data)        current_node2 = current_node2.next    return merged_list # Example usage: list1 = LinkedList() list1.append(1) list1.append(3) list1.append(5) list2 = LinkedList() list2.append(2) list2.append(4) list2.append(6) print("Linked List 1:") list1.display()  # Output: 1 -> 3 -> 5 -> None print("Linked List 2:") list2.display()  # Output: 2 -> 4 -> 6 -> None merged_list = merge_sorted_lists(list1, list2) print("Merged Sorted Linked List:") merged_list.display()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

In this implementation, the merge_sorted_lists function takes two sorted linked lists as input arguments and returns a new merged sorted linked list. It compares the nodes of both linked lists and appends the smaller data value to the merged_list. The function continues this process until it reaches the end of both input lists.

The time complexity of this merge operation is O(n + m), where n and m are the number of nodes in the two linked lists, respectively. This is because we need to traverse both lists once to form the merged list. The operation itself is efficient and takes linear time.