Remove Duplicates from Sorted List

Remove duplicate elements from a sorted linked list.

Example:

Input:  1->1->2->2->4->5->5
Output: 1->2->4->5

Approach

Java

public class RemoveDuplicatesFromSortedList {
    public static void main(String[] args) {
        ListNode l = new ListNode(1);
        l.next = new ListNode(1);
        l.next.next = new ListNode(2);
        l.next.next.next = new ListNode(2);
        l.next.next.next.next = new ListNode(4);
        l.next.next.next.next.next = new ListNode(5);
        l.next.next.next.next.next.next = new ListNode(5);
        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) {
        // If list is null
        if (head == null) {
            return head;
        }

        ListNode root = head;
        ListNode prev = root;
        int cnt = 0;
        // Iterate till end of list
        while (root != null) {
            prev = root;
            root = root.next;
            cnt = 1;
            // Iterate till end of list and duplicate
            while (root != null && prev.val == root.val) {
                cnt++;
                root = root.next;
            }
            if (cnt > 1) {
                prev.next = root;
                prev = root;
            }
        }
        return head;
    }
}

class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

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

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
// Time Complexity : O(n)
// Space Complexity : O(1)

C++

#include <bits/stdc++.h>
using namespace std;
struct ListNode
{ 
   int val;
   ListNode *next;
   ListNode(int data)
    {
        this->val=data;
        this->next=NULL;
    }
};
void linkedListTraversal(ListNode *node)
{
        while (node != NULL) {
            cout<<node->val<<" ";
            node = node->next;
        }
}
ListNode* removeDuplicateElement(ListNode *head) 
{
    // If list is null
    if (head==NULL) {
        return head;
        }

    ListNode *root = head;
    ListNode *prev = root;
    int cnt = 0;
    // Iterate till end of list
    while (root != NULL) 
    {
        prev = root;
        root = root->next;
        cnt = 1;
            // Iterate till end of list and duplicate
          while (root != NULL&& prev->val == root->val) {
                cnt++;
                root = root->next;
            }
            if (cnt > 1) {
                prev->next = root;
                prev = root;
            }
       }
   return head;
}
int main()
{
        ListNode *head = new ListNode(1);
        head->next = new ListNode(1);
        head->next->next = new ListNode(2);
        head->next->next->next = new ListNode(2);
        head->next->next->next->next = new ListNode(4);
        head->next->next->next->next->next = new ListNode(5);
        head->next->next->next->next->next->next = new ListNode(5);
        head = removeDuplicateElement(head);
        cout<<"After Removing :\n";
        linkedListTraversal(head);
}