Java remove duplicates from linked list

Question

I want to remove duplicates from sorted linked list {0 1 2 2 3 3 4 5}.

`

public Node removeDuplicates(Node header)
{
    Node tempHeader = null;
    if(header != null) 
        tempHeader = header.next;
    else return header;
    Node prev = header;
    if((tempHeader == null)) return header ;

    while(tempHeader != null)
    {
        if(tempHeader.data != prev.data)
        {
            prev.setNext(tempHeader);
        }
    tempHeader = tempHeader.next;
    }
    prev = header;
    printList(prev);
    return tempHeader;
}

`

prev.setNext(tempHeader) is not working correctly inside the while loop. Ideally when prev = 2 and tempHeader = 3, prev.next should be node with data = 3.

Printlist function just takes header pointer and prints the list.

Node definition is given below.

public class Node
{
    int data;
    Node next;

    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

Is this homework? If so, please tag it with the [homework] tag. — Louis Wasserman
– Louis Wasserman, Commented Feb 27, 2012 at 3:11
No, this is not homework. I found one PDF on stanford website which contains 18 linked list problems and one of them is removeDuplicate program. here is the link; cslibrary.stanford.edu/105/LinkedListProblems.pdf — Junaid
– Junaid, Commented Feb 27, 2012 at 3:26
You are not calling prev.next anywhere. You are just calling prev.setNext(tempHeader) inside while loop. — Kuldeep Jain
– Kuldeep Jain, Commented Feb 27, 2012 at 3:50

BillRobertson42 · Accepted Answer · 2012-02-27 03:53:22Z

1

The loop is sorted, so you know that duplicates are going to sit next to each other. If you want to edit the list in place then, you've got to have two list pointers (which you do). The one you call tempHeader and prev, and you've got to advance them both in the the list as you go (which I don't see in the code). Otherwise, if you don't advance the prev pointer as you go, then you're always comparing the element under tempHeader to the first item in the list, which is not correct.

An easier way to do this, however, is to build a new list as you go. Simply remember the value of the last item that you appended to the list. Then if the one that you're about to insert is the same then simply don't insert it, and when you're done, just return your new list.

edited Feb 27, 2012 at 3:53

answered Feb 27, 2012 at 3:37

BillRobertson42

12.9k4 gold badges44 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gmhk · Accepted Answer · 2012-02-27 03:15:38Z

1

I can give you 2 suggestions for the above suggestion 1) Convert the linked List to Set, that will eliminate the duplicates and Back from Set to the Linked list Code to get this done would be

linkedList = new LinkedList<anything>(new HashSet<anything>(origList));

2) You can use LinkedHashSet, if you dont want any duplicates

answered Feb 27, 2012 at 3:15

gmhk

16k29 gold badges91 silver badges113 bronze badges

2 Comments

Junaid Over a year ago

that sounds good but can we do the way I am trying to do. I think, we can do in C/C++ this way. Isn't so?

user684934 Over a year ago

-1: This completely ignores the fact that the list is sorted, AND requires sorting afterwards (unless, of course, you use LinkedHashSet, but either way it is way more expensive than a single linear pass).

Joop Eggen · Accepted Answer · 2012-02-27 03:40:49Z

1

In this case no return value is needed.

public void removeDuplicates(Node list) {
    while (list != null) {
        // Walk to next unequal node:
        Node current = list.next;
        while (current != null && current.data.equals(list.data)) {
            current = current.next;
        }
        // Skip the equal nodes:
        list.next = current;
        // Take the next unequal node:
        list = current;

    }
}

answered Feb 27, 2012 at 3:40

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

1 Comment

Kuldeep Jain Over a year ago

+1 This will do the job, except current.data.equals(list.data) should change to current.data == list.data

logi-kal · Accepted Answer · 2016-08-07 10:58:13Z

1

public ListNode removeDuplicateElements(ListNode head) {
  if (head == null || head.next == null) {
        return null;
    }
    if (head.data.equals(head.next.data)) {
        ListNode next_next = head.next.next;
        head.next = null;
        head.next = next_next;
        removeDuplicateElements(head);
    } else {
        removeDuplicateElements(head.next);
    }
    return head;
}

edited Aug 7, 2016 at 10:58

logi-kal

7,8996 gold badges35 silver badges48 bronze badges

answered Aug 7, 2016 at 9:08

Abhishek Chaurasia

8767 silver badges4 bronze badges

Comments

lio · Accepted Answer · 2020-03-28 15:48:46Z

By DoublyLinked List and using HashSet,

  public static void deleteDups(Node n) {
    HashSet<Integer> set = new HashSet<Integer>();
    Node previous = null;
    while (n != null) {
        if (set.contains(n.data)) {
            previous.next = n.next;
        } else {
            set.add(n.data);
            previous = n;
        }
        n = n.next;
    }
}

doublylinkedList

class Node{

public Node next;
public Node prev;
public Node last;
public int data;
public Node (int d, Node n, Node p) {
    data = d;
    setNext(n);
    setPrevious(p);
}

public Node() { }

public void setNext(Node n) {
    next = n;
    if (this == last) {
        last = n;
    }
    if (n != null && n.prev != this) {
        n.setPrevious(this);
    }
}

public void setPrevious(Node p) {
    prev = p;
    if (p != null && p.next != this) {
        p.setNext(this);
    }
}}

Sushil Kumar · Accepted Answer · 2025-02-19 02:41:14Z

0

Node removeDuplicates(Node head){
    Node temp = head;
    Node prev = null;
    while(temp!=null){
        prev = temp;
        temp = temp.next;
        if(temp!=null&&temp.data==prev.data){
            while(temp!=null && temp.data==prev.data){
                temp = temp.next;
            }
            prev.next=temp;
        }
    }
     return head;
}

answered Feb 19 at 2:41

Sushil Kumar

1

1 Comment

Mark Rotteveel Feb 19 at 11:36

Although this code might answer the question, I recommend that you also provide an explanation what your code does and how it solves the problem of the question. Answers with an explanation are usually more helpful and of better quality, and are more likely to attract upvotes.

Collectives™ on Stack Overflow

Java remove duplicates from linked list

6 Answers 6

Comments

2 Comments

1 Comment

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

2 Comments

1 Comment

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related