Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Remove Duplicates from an Unsorted Linked list

Objec­tive: Write a pro­gram to remove the dupli­cates from an unsorted linked list

Exam­ple:

Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3

Input: An unsorted linked list

Out­put: Linked list with no duplicates.

Approach:

  • Cre­ate a Hash Table
  • Take two point­ers, pre­vN­ode and CurrNode.
  • Pre­vN­ode will point to the head of the linked list and cur­rN­ode will point to the head.next.

  • Now nav­i­gate through the linked list.
  • Check every node data is present in the HashTable.
  • if yes then delete that node using pre­vN­ode and currNode.
  • If No, then insert that node data into the linked list
  • Return the head of the list

Time Com­plex­ity : O(n)
Space Com­plex­ity : O(n)

Fol­low Up: If sup­pose addi­tion buffer is not allowed then we have option but to check every node data against every other node data and if find dupli­cates, delete that node.
Time Com­plex­ity : O(n^2)

Com­plete Code for the Hash Table method:


Out­put:

Original List : ->1->2->2->3->4->4->2
Updated List: ->1->2->3->4

You may also like...

  • deen john

    Hi , I think there is one prob­lem with the code .Though the result is cor­rect but cur­rent Node would still point to next so it won’t be garbage col­lected .Instead cur­rent node.next should be equal to null to make it garbage col­lected. I have com­mented the cor­rect solution :

    while(currNode!=null){
    int data = currNode.data;
    if(ht.contains(data)){
    prevNode.next = currNode.next;

    //temp= cur­rN­ode;
    cur­rN­ode = currNode.next;
    //temp.next=null;

    • Aditi Man­gal

      There is another prob­lem with this code.try run­ning the code with this list : 2223442
      the out­put com­ing is: 2234 while it should be 234

      • tuto­ri­al­hori­zon

        Hi Aditi, Thanks for point­ing the prob­lem, i have cor­rected the code. Please let me know if you find prob­lems in other posts.

  • deen john

    Hi , I think there is one prob­lem with the code .Though the result is cor­rect but cur­rent Node would still point to next so it won’t be garbage col­lected .Instead cur­rent node.next should be equal to null to make it garbage col­lected. I have com­mented the cor­rect solution :

    while(currNode!=null){
    int data = currNode.data;
    if(ht.contains(data)){
    prevNode.next = currNode.next;

    //temp= cur­rN­ode;
    cur­rN­ode = currNode.next;
    //temp.next=null;
    Please let me know if i am wrong

    • tuto­ri­al­hori­zon

      Thanks John, some­how i missed you com­ment, Imple­mented your sug­ges­tion. Thanks

  • http://www.bitsa.in/ Aravind

    Why are you using Hash instead of Array? @tutorialhorizon

  • Alex Chebykin

    There actu­ally exists a solu­tion with time com­plex­ity O(n + m) and space com­plex­ity O(1).
    Hint: sup­pose the lists are the same length.
    Actual solu­tion:
    NodeList findIntersectionNoMemoryElegant(NodeList other) {
    int thisLen = find­Length();
    int oth­erLen = other.findLength();
    NodeList fst = this;
    NodeList snd = other;
    int diff = thisLen — oth­erLen;
    while (diff > 0) {
    fst = fst.next;
    diff–;
    }
    while (diff < 0) {
    snd = snd.next;
    diff++;
    }
    while (fst != null && snd != null) {
    if (fst == snd) return fst;
    fst = fst.next;
    snd = snd.next;
    }
    return null;
    }