Lecture 191:-Remove Duplicates from Sorted Link List

 

To remove duplicates from a sorted singly linked list, we can traverse the list and remove any consecutive duplicate nodes. Since the list is sorted, all duplicate elements will be grouped together.

 

Here's how you can implement this 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 = self.head            while current.next:                current = current.next            current.next = new_node    def remove_duplicates(self):        if not self.head:            return        current = self.head        while current.next:            if current.data == current.next.data:                current.next = current.next.next            else:                current = current.next    def display(self):        current = self.head        while current:            print(current.data, end=" -> ")            current = current.next        print("None") # Example usage: if __name__ == "__main__":    linked_list = LinkedList()    # Append elements to create the sorted linked list with duplicates    linked_list.append(1)    linked_list.append(1)    linked_list.append(3)    linked_list.append(3)    linked_list.append(5)    linked_list.append(7)    linked_list.append(7)    linked_list.append(7)    print("Original Linked List:")    linked_list.display()    linked_list.remove_duplicates()    print("Linked List after removing duplicates:")    linked_list.display()

In this example, we have implemented the Node and LinkedList classes. The LinkedList class has a remove_duplicates method that removes duplicates from the sorted linked list.

We then create a linked list object and use the append method to add elements (1, 1, 3, 3, 5, 7, 7, and 7) to create the sorted linked list with duplicates. We then call the remove_duplicates method to remove duplicates from the linked list.

The output will be:

rustCopy code

Original Linked List: 1 -> 1 -> 3 -> 3 -> 5 -> 7 -> 7 -> 7 -> None Linked List after removing duplicates: 1 -> 3 -> 5 -> 7 -> None

The linked list is modified to remove the consecutive duplicates, resulting in the final linked list with elements 1, 3, 5, and 7.