removing duplicates in linked list

Question

I tried out the following code in java to remove duplicates from a linked list

public static LinkedListNode<Integer> removeDuplicates(LinkedListNode<Integer> head) {
    LinkedListNode<Integer> ptr1=head;
    LinkedListNode<Integer> ptr2=head.next;
    if(head==null)
        return null;
    if(head.next==null)
        return head;
    while(ptr2!=null){
        if(ptr1.data==ptr2.data){
            ptr2=ptr2.next;
        }else{
            ptr1.next=ptr2;
            ptr1=ptr2;
            ptr2=ptr2.next;
        }
    }
    ptr1.next=ptr2;
    return head;
}

which takes the head of the linked list as input then after removing duplicates from it returns the head.

if we take the following sample input for a linked list

281 386 386 957 1022 1216 1232 1364 1428 1428 1428 1428 1501 1953

it's not removing duplicates as expected

I tried debugging it in vscode and was amazed to see that ptr1.data == ptr2.data evaluates to false when ptr1 is at 386 and ptr2 is at the 386 after the first 386 of the input I also tried a getter for LinkedListNode even then ptr1.getData()==ptr2.getData() was coming out false

is there some concept related to memory allocation I'm not getting involving heaps or something?

if you're curious about the LinkedListNode class and the function used to create the linked list here they are:

public class LinkedListNode<T> {
T data;
LinkedListNode<T> next;
LinkedListNode (T data){
    this.data=data;
}
T getData(){
    return this.data;
}
}

and

static LinkedListNode<Integer> takeinput(){
    Scanner sc = new Scanner(System.in);
    int data = sc.nextInt();
    LinkedListNode<Integer> head = new LinkedListNode<Integer>(data);
    LinkedListNode<Integer> tail = head;
    data=sc.nextInt();
    while(data!=-1){
        LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(data);
        if(head.next==null){
            head.next=newNode;
            tail=newNode;
        }else{
            tail.next=newNode;
            tail= newNode;
        }
        data=sc.nextInt();
    }
    sc.close();
    return head;   
}

input:281 386 386 957 1022 1216 1232 1364 1428 1428 1428 1428 1501 1953 -1 it stops to take input after -1 is entered and returns the head of the generated linkedlist

You are aware of the differences between `==` and `equals()` in Java? `==` tests for *identity*, and your duplicates may be *equal*, but they are never *identical* – as your program points out clearly. — tquadrat, Apr 18 '20 at 17:44
The simplest way to remove duplicates is to put everything into a set and then put this set into an LinkedList. — Reddi, Apr 18 '20 at 17:50
thank you @tquadrat that was the issue now its working fine,I had forgotten about the Integer object part — Omnicacorp, Apr 18 '20 at 18:06
Does this answer your question? [What is the difference between == and equals() in Java?](https://stackoverflow.com/questions/7520432/what-is-the-difference-between-and-equals-in-java) — Arvind Kumar Avinash, Jun 24 '20 at 16:15
why is your data is of type T? If its all numbers that's stored in Linked List, why don't you declare it as integer? That should solve your == problem. This of course looks like an interview question, so you can very well work with numbers. Just like others pointed out, you should defenitely know the difference between == and equals(). — Raj V, Jun 30 '21 at 04:37

backdoor · Answer 1 · 2020-04-18T18:20:06.930

There should be 2 While loop to pick one element and check if the element exists in the Linked List. Following code may help you understand better.

LinkedListNode<Integer> ptr1=head;
        LinkedListNode<Integer> ptr2=head.next;
        if(head==null)
            return null;
        if(head.next==null)
            return head;

        while (ptr1 != NULL && ptr1.next != NULL) // pick 1 element at time
        { 
            ptr2 = ptr1; 
            while (ptr2.next != NULL) 
            { 
                if (ptr1.data == ptr2.next.data) // check if the element exits in LinkedList or not
                { 
                    dup = ptr2.next; 
                    ptr2.next = ptr2.next.next; 

                } 
                else 
                    ptr2 = ptr2.next; 
            } 
            ptr1 = ptr1.next; 
        } 
        return head;

This code `ptr1.data == ptr2.next->data` does not appear to be Java :) — Nowhere Man, Apr 18 '20 at 18:18
@AlexRudenko Thanks for pointing out the error. It was done in C++ — backdoor, Apr 18 '20 at 18:21

score 0 · Answer 2 · answered Apr 18 '20 at 18:06

0

If I just read your title you can remove duplicates from LinkedList by iterate over , store value in a Set and check for duplicates via the Set if contains return true call remove on the integrator.

Iterator iter = list.iterator();
Set set = new HashSet();
while (iter.hasNext())
 {

  Object obj = iter.next();
  if(set.contains(obj))){
        iter.remove();
  }else{
        set.add(obj);
      }
  }

answered Apr 18 '20 at 18:06

CodeScale

3,046
1
12
20

thank you for the answer i forgot to mention that there was a requirement of O(1) space complexity your answer would be the best otherwise though – Omnicacorp Apr 18 '20 at 18:09

score 0 · Answer 3 · answered Apr 18 '20 at 18:25

0

remove duplicate

list.stream().distinct().peek(System.out::println).collect(Collectors.toList());

answered Apr 18 '20 at 18:25

Ng Sharma

2,072
8
27
49

1

There's one minor moment:OP's list is not implementing `` from Collections Framework and does not have stream() as such ¯ \ _ (ツ) _ / ¯ – Nowhere Man Apr 18 '20 at 18:36

score 0 · Accepted Answer · answered Apr 18 '20 at 18:32

This update is too late but it does not have NPE:

public static LinkedListNode<Integer> removeDuplicates(LinkedListNode<Integer> head) {
    if (head == null || head.next == null)
        return head;

    LinkedListNode<Integer> ptr1 = head;
    LinkedListNode<Integer> ptr2 = head.next;

    while (ptr2 != null) {
        while(ptr1.data.equals(ptr2.data)) {
            ptr2 = ptr2.next;
            ptr1.next = ptr2;
        }
        ptr1.next = ptr2;
        ptr1 = ptr2;
        ptr2 = ptr2.next;

    }
    ptr1.next = ptr2;
    return head;
}

score 0 · Answer 5 · answered Jun 30 '21 at 03:27

Without using extra space, just iterating through the linkedlist once per node can server the purpose

public void removeDupsFromLinkedList(Node head)
    {
        LinkedListImpl linkedListImpl = new LinkedListImpl();
        if(head==null)
            return;
        Node temp = head;
        while(temp!=null)
        {
            Node traverseNode = temp;
            while(traverseNode!=null)
            {
                if(traverseNode.value==temp.value && traverseNode!=temp)
                    linkedListImpl.deleteNode(traverseNode);
                traverseNode=traverseNode.next;
            }
            temp = temp.next;
        }
    }

removing duplicates in linked list

5 Answers5