Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example:

Input:  1->1->1->2->3->NULL
Output: 2->3->NULL

Approach

Java

public class RemoveDuplicatesFromSortedListII {
    public static void main(String[] args) {
        ListNode l = new ListNode(1);
        l.next = new ListNode(1);
        l.next.next = new ListNode(1);
        l.next.next.next = new ListNode(2);
        l.next.next.next.next = new ListNode(3);
        ListNode node = removeDuplicateElement(l);
        System.out.println("After Removing :");
        linkedListTraversal(node);
    }

    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    public static ListNode removeDuplicateElement(ListNode head) {
        ListNode root = null, temp = head;
        if (head == null)
            return head;
        ListNode prev = null, temp1 = null;
        int flag = 0;
        int x;
        int cnt;
        while (temp != null) {
            prev = temp;
            x = prev.val;
            temp = temp.next;
            cnt = 1;
            while (temp != null && (temp.val == x)) {
                cnt++;
                temp = temp.next;
            }

            if (cnt == 1) {

                if (flag == 0) {
                    root = prev;
                    temp1 = root;
                    flag = 1;
                } else {
                    temp1.next = prev;
                    temp1 = temp1.next;
                }
            }

        }
        if (temp1 != null)
            temp1.next = null;
        return root;
    }
}

class ListNode {
    int val;
    ListNode next;
    

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};


//function to remove the duplicate elements
//in linked list
Node* deleteDuplicates(Node* head)
{
        Node *root=NULL,*temp=head;
        if(head==NULL)
              return head;
       Node *prev=NULL,*temp1=NULL;
        int flag=0;
        int x;
        int cnt;
        while(temp!=NULL)
         {
            prev=temp;
           x=prev->data;
            temp=temp->next;
           cnt=1;
            while(temp!=NULL&&(temp->data==x))
            {
                cnt++;
                temp=temp->next;
            }
        
            if(cnt==1)
            {

                if(flag==0)
                {
                    root=prev;
                    temp1=root;
                    flag=1;
                }
               else
               {
                  temp1->next=prev;
                   temp1=temp1->next;
               }
            }

        }
        if(temp1!=NULL)
           temp1->next=NULL;
        return root;
}

//function to traverse a linked 
//list
void linkedListTraversal(Node *head)
{
    Node *temp=head;
    //iterate till we reach end of the linked 
    //list
    while(temp!=NULL)
     {
         //print the current
         //node data
         cout<<temp->data<<" ";
         //move to next node
         temp=temp->next;
     }
}
int main()
{
    Node *head=new Node(1);
    head->next=new Node(1);
    head->next->next=new Node(1);
    head->next->next->next=new Node(2);
    head->next->next->next->next=new Node(3);

    head=deleteDuplicates(head);
    linkedListTraversal(head);
    return 0;

}