Remove occurrences in Linked List Editorial

Practice Problem Link: Remove Occurrences in Linked List

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

Problem Statement

Given a linked list and a key, remove all occurrences of the key from the Linked List. Return the head of the resultant list.

Approach

The idea is to simply traverse the given linked list and delete all the occurrences of the key one by one.

Note: If the head node is equal to the key then move the head pointer to the first node which is not equal to the key and then follow the above step.

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* removeOccurences(ListNode* head, int key) {
	while (head != NULL && head->data == key) {
		head = head->next;
	}
	ListNode* currentNode = head;
	while (currentNode != NULL && currentNode->next != NULL) {
		if (currentNode->next->data == key) {
			currentNode->next = currentNode->next->next;
		}
		else {
			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 removeOccurences(ListNode head, int key) {
		while (head != null && head.data == key) {
			head = head.next;
		}
		ListNode currentNode = head;
		while (currentNode != null && currentNode.next != null) {
			if (currentNode.next.data == key) {
				currentNode.next = currentNode.next.next;
			}
			else {
				currentNode = currentNode.next;
			}
		}
		return head;
	}
}