How to Remove Duplicates (Linked List)

Photo by Matthew Henry on Unsplash

Hey guys, Today we are going to take a look into the Removing Duplicates Problem in Linked List. I have given you the code and have explained how the code works. If you have any doubts regarding this. I will clear it within a day.

Before we get into the problem. I have published an ebook. A compilation of 100 Java(Interview)Programming problems which have been solved . I have given clear explanation and the code in the book.

Trust me when I say, this will be a kick start for you to achieve the job at your dream company.

Click on this link to get you to the landing page. It is completely free when you use kindle amazon. Take a look at it.

AIM

Given a Linked-list (where each node has a character) remove duplicates characters and maintain the same order

Input: H->e->l->l->o->w->o->r->l->d->h->i->NULL

Output: H->e->l->o->w->r->d->h->i->NULL

Code:

public class Answer implements QuestionInterface {

@Override

public SchNode func(SchNode str){

SchNode p1=null;

SchNode p2=null;

SchNode dup=null;

p1=str;

while (p1 != null && p1.nextNode != null) {

p2 = p1;

while (p2.nextNode != null) {

if (p1.ch == p2.nextNode.ch) {

dup = p2.nextNode;

p2.nextNode = p2.nextNode.nextNode;

}

else {

p2 = p2.nextNode;

}

}

p1 = p1.nextNode;

}

return str;

}

}

Explanation

The problem is to remove the duplicate characters in the list and still maintain the same order in the list. The each node of the list has a character stored in it.

Each character in the list is checked with the other character in list and if the character is repeated then the node that has the same character is deleted from the list and the pointer of the previous node of the deleted node is linked to the next node of the deleted node.

Algorithm:

  • The input list is passed to the func(SchNode str)
  • Using the while loop and condition being the current node and next node of the current node not null the list is being checked.
  • Now the characters of the input string is compared using the(p1.ch == p2.nextNode.ch) condition where p1 is initialized with the head value of the list and
  • When the character is repeated then the node storing that character is deleted.
  • Now the pointer of the previous node of the deleted node is pointed to the next node of the deleted node.
  • The loop iterates till the end of the list .
  • Now the new output list is sent as output to the user.

Conclusion

You can follow House of Codes to receive updates when we post new coding challenges. Also you could send us your solutions or your ideas for any coding challenge. We would be thrilled to read them. ;)

Author: Architha Harinath
Editor : Akshay Ravindran

Code -> Understand-> Repeat is my motto. I am a Data Engineer who writes about everything related to Data Science and Interview Preparation for SDE.

Code -> Understand-> Repeat is my motto. I am a Data Engineer who writes about everything related to Data Science and Interview Preparation for SDE.