Lecture 197:-  Concatenating 2 Linked Lists

To concatenate two linked lists, you need to simply link the last node of the first linked list to the head of the second linked list. This operation can be performed in constant time since you only need to update one pointer.

Here's the Python code to concatenate two linked lists:

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 concatenate_lists(list1, list2):    if not list1.head:        list1.head = list2.head    else:        current_node = list1.head        while current_node.next:            current_node = current_node.next        current_node.next = list2.head # Example usage: list1 = LinkedList() list1.append(1) list1.append(2) list1.append(3) list2 = LinkedList() list2.append(4) list2.append(5) print("Linked List 1:") list1.display()  # Output: 1 -> 2 -> 3 -> None print("Linked List 2:") list2.display()  # Output: 4 -> 5 -> None concatenate_lists(list1, list2) print("Concatenated Linked List:") list1.display()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None

In this implementation, the concatenate_lists function takes two linked lists as input arguments. It checks if the first linked list is empty. If it is empty, it sets the head of the first linked list to the head of the second linked list. Otherwise, it traverses the first linked list to find the last node and then links it to the head of the second linked list.

The time complexity of this operation is O(n), where n is the number of nodes in the first linked list. This is because we need to traverse the first linked list to find its last node. The operation itself is efficient and takes constant time for updating the pointer to the head of the second linked list.