You are given a class singleLinkedList implementing single-linked lists, which c

Question

You are given a class singleLinkedList implementing single-linked lists, which contains a head data field referencing the list itself and an inner class Node which contains a data field data and a reference to the next node next. Write in pseudo-code or Java a method with signature: public void removeAdjacentDuplicates() that removes all adjacent nodes whose data field contain the same values. For example, the result of removing the adjacent duplicates in the list [1, 2, 2, 3, 4, 4, 4] should be [1, 2, 3, 4].

Explanation / Answer

I have this simple solution, where we will use 2 loops.

The Outer loop is used to pick the elements of list one by one and the inner loop used to compare the picked up element of the list with rest of the elements in the list.

// Java program to remove adjancent duplicates from
// linked list

class LinkedList {

static class Node {

       int data;
       Node next;

       Node(int d) {
           data = d;
           next = null;
       }
   }

   static Node head; // this is the staic declaration of the node's head.

   /* Function to remove adjacent duplicates from linked list */
   void removeAdjacentDuplicates() {
       Node ptr1 = null, ptr2 = null, dup = null;
       ptr1 = head;

       /* here we will pick the elements of the list one by one by iterating through the list */
// firstly check wheather the node is not null

while (ptr1 != null && ptr1.next != null) {
           ptr2 = ptr1;

           /* Now we compare the picked element with rest
               of the elements */
           while (ptr2.next != null) {

               /* this condition is used to delete the duplicate if found */
               if (ptr1.data == ptr2.next.data) {

                   /* sequence of steps is important here */

dup = ptr2.next;

                   ptr2.next = ptr2.next.next;
                   System.gc();
               } else /* This is tricky */ {
                   ptr2 = ptr2.next;
               }
           }
           ptr1 = ptr1.next;
       }
   }

// this function is used to print the list.

   void printList(Node node) {
       while (node != null) {
           System.out.print(node.data + " ");
           node = node.next;
       }
   }

   public static void main(String[] args) {
// here we test our program

LinkedList list = new LinkedList();
       list.head = new Node(1);
       list.head.next = new Node(2);
       list.head.next.next = new Node(2);
       list.head.next.next.next = new Node(3);
       list.head.next.next.next.next = new Node(4);
       list.head.next.next.next.next.next = new Node(4);
       list.head.next.next.next.next.next.next = new Node(4);

       System.out.println("Original Linked list : ");
       list.printList(head);

       list.removeAdjacentDuplicates();
       System.out.println("");
       System.out.println("After removinf duplicates : ");
       list.printList(head);
   }
}

Outptut:

Original Linked list :

After removing duplicates :

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.