Question

Write a removeDuplicates() method for the LinkedList class we saw in lecture. The method will remove all duplicate elements from the LinkedList by removing the second and subsequent elements. If there is only one copy of an element, it is not removed. The list size should shrink accordingly based on the number of duplicates removed.

Answer 1

Answer:

removeDuplicates() function:-

//removeDuplicates() function removes duplicate elements form linked list.

   void removeDuplicates() {

     

       //declare 3 ListNode pointers ptr1,ptr2 and duplicate.

       //initially, all points to null.

       ListNode ptr1 = null, ptr2 = null, duplicate = null;

       

       //make ptr1 equals to head.

       ptr1 = head;

        //run while loop till ptr1 points to second last node.

       //pick elements one by one..

       while (ptr1 != null && ptr1.next != null)

       {

               // make ptr2 equals to ptr1.

               //or make ptr2 points to same node as ptr1.

           ptr2 = ptr1;

           //run second while loop to compare all elements with above selected element(ptr1->val).

           while (ptr2.next != null)

           {

              //if element pointed by ptr1 is same as element pointed by ptr2.next.

               //Then, we have found duplicate element.

               //Now , we have to remove this duplicate element.

               if (ptr1.val == ptr2.next.val)

               {

                  //make duplicate pointer points to node where ptr2.next points(duplicate node).

                       duplicate = ptr2.next;

                       //change links to remove duplicate node from linked list.

                       //make ptr2.next points to duplicate.next.

                   ptr2.next = duplicate.next;

               }

               

             //if element pointed by ptr1 is different from element pointed by ptr2.next.

               //then it is not duplicate element.

               //So, move ptr2 = ptr2.next.

               else

               {

                   ptr2 = ptr2.next;

               }

           }

           

           //move ptr1 = ptr1.next, after check duplicate elements for first node.

           //Now, we check duplicacy for second node and so on.

           //so, move ptr1  by one node.

           ptr1 = ptr1.next;

       }

   }

Explanation:

Complete Code:-

//Create Linked List Class.

class LinkedList {

       //Create head pointer.

       static ListNode head;

       //define structure of ListNode.

       //it has int val(data) and pointer to ListNode i.e, next.

   static class ListNode {

       int val;

       ListNode next;

       //constructor to  create and initialize a node.

       ListNode(int d) {

               val = d;

           next = null;

       }

   }

//removeDuplicates() function removes duplicate elements form linked list.

   void removeDuplicates() {

       

       //declare 3 ListNode pointers ptr1,ptr2 and duplicate.

       //initially, all points to null.

       ListNode ptr1 = null, ptr2 = null, duplicate = null;

       

       //make ptr1 equals to head.

       ptr1 = head;

       

       

       //run while loop till ptr1 points to second last node.

       //pick elements one by one..

       while (ptr1 != null && ptr1.next != null)

       {

               // make ptr2 equals to ptr1.

               //or make ptr2 points to same node as ptr1.

           ptr2 = ptr1;

           //run second while loop to compare all elements with above selected element(ptr1->val).

           while (ptr2.next != null)

           {

              //if element pointed by ptr1 is same as element pointed by ptr2.next.

               //Then, we have found duplicate element.

               //Now , we have to remove this duplicate element.

               if (ptr1.val == ptr2.next.val)

               {

                  //make duplicate pointer points to node where ptr2.next points(duplicate node).

                       duplicate = ptr2.next;

                       

                       //change links to remove duplicate node from linked list.

                       //make ptr2.next points to duplicate.next.

                   ptr2.next = duplicate.next;

               }

               

             //if element pointed by ptr1 is different from element pointed by ptr2.next.

               //then it is not duplicate element.

               //So, move ptr2 = ptr2.next.

               else

               {

                   ptr2 = ptr2.next;

               }

           }

           

           //move ptr1 = ptr1.next, after check duplicate elements for first node.

           //Now, we check duplicacy for second node and so on.

           //so, move ptr1  by one node.

           ptr1 = ptr1.next;

       }

   }

   //display() function prints linked list.

   void display(ListNode node)

   {

       //run while loop till last node.

       while (node != null)

       {

               //print node value of current node.

           System.out.print(node.val + " ");

           

           //move node pointer by one node.

           node = node.next;

       }

   }

   public static void main(String[] args) {

       

       //Create object of Linked List class.

       LinkedList list = new LinkedList();

       

       //first we create nodes and connect them to form a linked list.

       //Create Linked List 1-> 2-> 3-> 2-> 4-> 2-> 5-> 2.

       

       //Create a Node having node data = 1 and assign head pointer to it.

       //As head is listNode of static type. so, we call head pointer using class Name instead of object name.

       LinkedList.head = new ListNode(1);

       

       //Create a Node having node data = 2 and assign head.next to it.

       LinkedList.head.next = new ListNode(2);

       LinkedList.head.next.next = new ListNode(3);

       LinkedList.head.next.next.next = new ListNode(2);

       LinkedList.head.next.next.next.next = new ListNode(4);

       LinkedList.head.next.next.next.next.next = new ListNode(2);

       LinkedList.head.next.next.next.next.next.next = new ListNode(5);

       LinkedList.head.next.next.next.next.next.next.next = new ListNode(2);

       //display linked list before Removing duplicates.

       System.out.println("Linked List before removing duplicates : ");

       list.display(head);

       //call removeDuplicates() function to remove duplicates from linked list.

       list.removeDuplicates();

       System.out.println("")

       //display linked list after Removing duplicates.

       System.out.println("Linked List after removing duplicates :  ");

       list.display(head);

   }

}

Output:-