Remove Duplicate Nodes from a Linked List - using Python

Problem: Remove duplicate nodes from a linked list. The list can be sorted or unsorted. Try to solve it most efficiently.

Solution

We are assuming that the given linked list is in the unsorted form. A node can be removed from a sorted linked list easily. That's why we will try the unsorted from first.

Make sure you already have known about the linked list and How to create a Linked List.

There are two methods to solve the problem.

Method 1:

In this case, two loops are needed. The first loop will iterate through the linked list and the second loop will compare every element picked up by the first loop with all the rest of the nodes in the linked list.

It's not the efficient way because in this case time complexity would be O(n^2). Let's see another method.

Method 2:

Solve the problem using the Hash table. Since we're solving this problem using python, we can use Python Set instead of the hash table because it contains only the unique items.

First, traverse the linked list from the head node and check if the value of the node is already presented in the hash table or not(In our case, a pre-declared python set). If the value is not present there then add it to the hash table else remove the node.

In this time, the time complexity would be O(n), which is much more efficient than the previous method. So, we're going to use this method to remove duplicate nodes from a linked list using python.

Code

'''Remove duplicate nodes from a linked list'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def addNode(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        temp = self.head
        while(temp.next):
            temp = temp.next
        temp.next = new_node

    def removeDuplicates(self):
        if self.head is None or self.head.next is None:
            return self.head
        
        current = self.head
        hash = set()

        hash.add(current.data)

        while(current.next is not None):
            if current.next.data in hash:
                current.next = current.next.next
            else:
                hash.add(current.next.data)
                current = current.next

        return self.head

    def printNode(self):
        temp = self.head
        while(temp):
            print(temp.data, end=' ')
            temp = temp.next

        print("\n")

if __name__ == "__main__":
    obj = LinkedList()
    # Add nodes
    obj.addNode(30)
    obj.addNode(40)
    obj.addNode(10)
    obj.addNode(20)
    obj.addNode(20)
    obj.addNode(35)

    print("Before Removing the Duplicate Nodes: ")
    obj.printNode()
   
    # Remove duplicate nodes
    obj.removeDuplicates()
    print("After Removing the Duplicate Nodes: ")
    obj.printNode()

Output

Before Removing Duplicate Nodes: 

10 20 30 40 20 

After Removing Duplicate Nodes: 

10 20 30 40 

Exercises For You

• Remove all the duplicate nodes from a linked list using the Method: 1.

• Remove all the duplicate nodes from a sorted linked list.