Linked List: Given a DLL, delete all the nodes that is greater than the given value

Problem Statement:

You are given a DLL and a number k, you need to delete all the nodes that is greater than k

Solution Explanation:

Solution is very simple.

Traverse the DLL one by one and get the pointer whose value is greater than x, then delete the node as we delete in the DLL.

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

Code Solution

#include <iostream> 
using namespace std;

struct Node 
{
	int data;
	Node *prev;
	Node *next;
};


void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node();

	new_node->data = new_data;

	new_node->prev = NULL;

	new_node->next = (*head_ref);

	if ((*head_ref) != NULL)
		(*head_ref)->prev = new_node;

	(*head_ref) = new_node;
}


void delete_node(Node** head_ref, Node* del)
{
	if (*head_ref == NULL || del == NULL)
		return;

	// if the node to be deleted 
	// is head node
	if (*head_ref == del)
		*head_ref = del->next;

	// if the node to be deleted 
	// is not the last node
	if (del->next != NULL)
		del->next->prev = del->prev;

	if (del->prev != NULL)
		del->prev->next = del->next;

	free(del);

	return;
}

void solution(Node** head_ref, int x)
{
	Node* ptr = *head_ref;
	Node* next;

	while (ptr != NULL) 
	{
		next = ptr->next;
		// if true, delete node 'ptr'
		if (ptr->data > x)
			delete_node(head_ref, ptr);
		ptr = next;
	}
}


void print_list(Node* head)
{
	while (head != NULL) 
	{
		cout << head->data << " ";
		head = head->next;
	}
}

int main()
{
	Node* head = NULL;

	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	push(&head, 2);
	push(&head, 1);

	int k = 3;

	cout << "Original List: ";
	print_list(head);

	solution(&head, k);

	cout << "\nResult List: ";
	print_list(head);
}

Output

Original List: 1 2 3 4 5 
Result List: 1 2 3