1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Flura [38]
3 years ago
11

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.
Computers and Technology
1 answer:
oksano4ka [1.4K]3 years ago
6 0

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:-

You might be interested in
Four workers take an extra half-hour for lunch, at a cost of $14/ hour
Usimov [2.4K]

Answer:

whats the rest ?

Explanation:

whats the rest ?

8 0
3 years ago
Hey plz help me with this<br>What is malware short for?​
soldier1979 [14.2K]

Answer:

Malware is the collective name for a number of malicious software variants, including viruses, ransomware and spyware. Shorthand for malicious software, malware typically consists of code developed by cyberattackers.

Explanation:

4 0
2 years ago
The design strategy that starts with a global view of the entire problem and breaks the problem down into smaller, more manageab
In-s [12.5K]

Answer:

Top down design

Explanation:

Top-down design is an approach that is used to break down the problem into the smaller subpart so that it can be manageable into more clear form.

C programming is the example of a top-down approach while C++ is the example of the bottom-up approach.

The advantages of the top-down design approach are:

1) easy to manage

2) easy to find the error

3) easy to debug

4 0
3 years ago
When a virtual machine is
egoroff_w [7]

Answer:

Resources, RAM

Explanation:

May be another choice for resources but the second one is definently RAM

8 0
3 years ago
Would an artificial intelligence come into existence anytime in the next 30 years?
Scrat [10]
Artificial Intelligence, based on neural networks, is available now.
4 0
3 years ago
Other questions:
  • Which rock band apologized for automatically adding its new album to every iPhone 6 in 2014
    8·2 answers
  • Which type of communication is usually handwriten
    11·2 answers
  • Access Control can be defined as putting controls (or countermeasures) in place to help achieve information security goals. Whic
    13·2 answers
  • Which type of loop is best if you do not know how many times you need the loop to run?
    8·1 answer
  • How would you classify an employee who is punctual, has respect for oneself and others, and takes initiative?
    13·2 answers
  • All nuclear energy results in the rapid release of energy, such as in atomic bombs. true or false
    8·1 answer
  • Demand is created through meeting customer buying criteria, credit terms, awareness (promotion) and accessibility (distribution)
    10·1 answer
  • What is the value of the variable result after these lines of code are executed?
    11·1 answer
  • Test if value is not less than 13.6.
    15·1 answer
  • What does the top level domain in a url inducate? A. The organization or company that owns the website. B. The organization or c
    6·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!