Remove Duplicates from Sorted Linked List - II Editorial

Practice Problem Link: Remove Duplicates from Sorted Linked List - II

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted linked list, remove all elements that have duplicates in the Linked List.

After the operation, only those elements should be there which were unique in the original list. Do not change the order of the linked list.

Approach

• Traverse the given list keeping a prevNode pointer up to the point where all the nodes have been checked. 
• If duplicate elements are found then go to the last duplicate node and assign the next pointer of the prevNode to the next pointer of this duplicate node. This will delete all the duplicate elements.
• If an element has a single occurrence then simply set the next pointer of prevNode to the current node. Make the current node as the prevNode and move to the next node.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* removeDuplicates(ListNode* head) {
	ListNode* prevNode = new ListNode(0);
    if (head == NULL || head->next == NULL) {
		return head;
	}
	ListNode* currentNode = head;
	head = prevNode;
    while (currentNode != NULL && currentNode->next != NULL) {
        if(currentNode->next != NULL && currentNode->next->data == currentNode->data){
        	while(currentNode->next != NULL && currentNode->next->data == currentNode->data){
                    currentNode = currentNode->next;
            }
            prevNode->next = currentNode->next;
        } else {
            prevNode->next = currentNode;
            prevNode = prevNode->next;
        }
        currentNode = currentNode->next;
    }
    return head->next;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode removeDuplicates(ListNode head) {
		ListNode prevNode = new ListNode(0);
		if (head == null || head.next == null) {
			return head;
		}
		ListNode currentNode = head;
		head = prevNode;
		while (currentNode != null && currentNode.next != null) {
			if(currentNode.next != null && currentNode.next.data == currentNode.data){
				while(currentNode.next != null && currentNode.next.data == currentNode.data){
						currentNode = currentNode.next;
				}
				prevNode.next = currentNode.next;
			} else {
				prevNode.next = currentNode;
				prevNode = prevNode.next;
			}
			currentNode = currentNode.next;
		}
		return head.next;
	}
}