Remove duplicates from an unsorted linked list

Given an unsorted linked list of N nodes. The task is to remove duplicate elements from this unsorted Linked List. When a value appears in multiple nodes, the node which appeared first should be kept, all others duplicates are to be removed.

Example 1:

Input:

N = 4

value[ ] = {5,2,2,4}

Output: 5 2 4

Example 2:

Input:

N = 5

value[] = {2,2,2,2,2}

Output: 2

My Code

def removeDuplicates(head):
        if head is None or not head.next:
            return head
        d = {}
        curr = head
        prev = None
        
        while curr.next:
            
            prev = curr
            curr = curr.next
            if curr.data in d:
                prev.next = curr.next
            else:
                d[curr.data] = 1
        return head

CodePudding user response：

In your while loop as condition you need curr instead of curr.next. And you need to overwrite curr at the end of the while loop. Like this:

def removeDuplicates(head):
    if head is None or not head.next:
        return head
    d = {}
    curr = head
    prev = None
    while curr:
        if curr.data in d:
            prev.next = curr.next
        else:
            d[curr.data] = 1
            prev = curr
        curr = curr.next
    return head