Remove Duplicates from Sorted Linked List Editorial

Practice Problem Link: Remove Duplicates from Sorted Linked List

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

Problem Statement

Given a sorted linked list, remove all duplicates from the Linked List.

After the operation, every element should appear only once. Do not change the order of the linked list.

Approach

Traverse the given linked list. While traversing compare each node with its next node. 

• If the next node is equal to the current node then delete the next node and compare the next to the next node with the current node. 
• If the next node is not equal to the current node then simply move the current node pointer 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* currentNode = head;
	while (currentNode != NULL && currentNode->next != NULL) {
		while (currentNode->next != NULL && currentNode->data == currentNode->next->data) {
			currentNode->next = currentNode->next->next;
		}
		currentNode = currentNode->next;
	}
	return head;
}

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 currentNode = head;
		while (currentNode != null && currentNode.next != null) {
			while (currentNode.next != null && currentNode.data == currentNode.next.data) {
				currentNode.next = currentNode.next.next;
			}
			currentNode = currentNode.next;
		}
		return head;
	}
}