How to delete nodes that have a greater value(s) on their right

Key takeaways:
The goal is to remove nodes from the linked list if there is any node with a greater value to their right. This is a common problem in competitive programming and interviews.
The brute force approach involves comparing each node to all nodes to its right. If any node has a greater value, the current node is deleted. This method has a time complexity of $O(n^2)$ , which can be inefficient for large lists.
A more optimized solution involves reversing the linked list first, then iterating through it while tracking the maximum value encountered. Nodes with values smaller than the maximum are deleted. Afterward, the list is reversed back to its original order. This approach improves efficiency, with a time complexity of $O(n)$ .
Both approaches have a constant space complexity of $O(1)$ , meaning they do not require extra space proportional to the size of the input, making them efficient in terms of memory usage.
The reversing approach is a clear optimization over the brute force method, making it more suitable for larger linked lists or when performance is crucial. It significantly reduces the time complexity from $O(n^2)$ to $O(n)$ .

Deleting nodes from a linked list with greater values on their right is a common problem in programming interviews and competitive coding. Let’s understand this problem using the following example.

Practical examples of deleting nodes that have a greater value(s) on their right

Here are practical examples where deleting nodes with greater values on their right is applied:

Stock price analysis: In a linked list of stock prices for consecutive days, deleting nodes with a greater price to the right can identify “local peaks.” This can help traders focus only on days where selling is optimal based on future price trends.
Game high scores: In a leaderboard stored as a linked list, removing scores that are less than a higher score on the right can highlight top scores achieved later, streamlining updates for dynamic ranking.
Weather data filtering: In a linked list of temperature readings for a week, deleting nodes with greater values to their right can isolate days with significant temperature drops, aiding in weather pattern predictions or alerts.
E-commerce discounts: In a list of product prices, removing nodes with higher discounts on the right helps retain only the best deals in a streamlined promotional list for display to users.
Memory management: When managing memory blocks, removing blocks with lower priority (values) in a linked list-like structure is common.

In this Answer, we'll explore two approaches to solve this problem.

Brute force approach

The brute force approach involves comparing each node with all subsequent nodes to its right. If any of those nodes have a greater value, the current node is deleted. This process continues until the end of the linked list is reached.

Algorithm

Here’s the step-by-step algorithm:

Start traversing the linked list from left to right.
Compare each node’s value with all subsequent nodes to its right.
Delete the current node if any of the subsequent nodes have a greater value.
Repeat this process for each node until the end of the linked list.

C++ and Python implementation

Below is the implementation of the algorithm in C++ and Python:

#include <iostream>
using namespace std;
class Node {
public:
    int value;
    Node* next;
    Node(int value) {
        this->value = value;
        next = nullptr;
    }
};
class LinkedList {
private:
    Node* head;
public:
    LinkedList() {
        head = nullptr;
    }
    void addNode(int value) {
        // Create a new node and make it the head
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }
    void printList() {
        Node* currentNode = head;
        while (currentNode) {
            cout << currentNode->value << " ";  // Print current node's value
            currentNode = currentNode->next;
        }
        cout << endl;
    }
    void deleteGreaterRight() {
        Node* currentNode = head;
        while (currentNode) {
            int currentValue = currentNode->value;
            bool found = false;
            Node* runner = currentNode->next;
            // Find a node with a greater value
            while (runner) {
                if (runner->value > currentValue) {
                    found = true;
                    break;
                }
                runner = runner->next;
            }
            if (found) {
                // Replace current node's value and skip the greater value node
                currentNode->value = runner->value;
                currentNode->next = runner->next;
                delete runner;  // Delete the node with greater value
            } else {
                // Move to the next node if no greater value was found
                currentNode = currentNode->next;
            }
        }
    }
};
int main() {
    LinkedList linkedList;
    linkedList.addNode(10);
    linkedList.addNode(5);
    linkedList.addNode(15);
    linkedList.addNode(9);
    linkedList.addNode(4);
    cout << "Given Linked List: ";
    linkedList.printList();
    linkedList.deleteGreaterRight();
    cout << "Linked list after deletion: ";
    linkedList.printList();
    return 0;
}

Implementation of the brute force approach in C++

Explanation

Let’s understand the above C++ code in detail.

Lines 1–13: This is the definition of the Node class, it defines a node with an integer value and a pointer to the next node.
Lines 15–22: The LinkedList class is defined. It has a constructor that initializes the head pointer to nullptr.
Lines 24–29: The addNode function adds a new node to the beginning of the linked list by creating a new node with the given value and updating the head pointer.
Lines 31–38: The printList function prints the values of all nodes in the linked list.
Lines 40–68: The deleteGreaterRight function deletes nodes with values less than any value to their right in the list. It iterates through each node in the list and compares its value to the values of the subsequent nodes. If a greater value is found, it replaces the current node’s value with the greater value and removes the node with the greater value. It deallocates the memory for the removed node.
Lines 70–87: The main function creates a LinkedList object and adds several nodes to it. Then it prints the initial list, calls the deleteGreaterRight function to modify the list, and finally prints the modified list.

Time complexity

The time complexity is $O(n^2)$ . It exhibits quadratic time complexity due to the deleteGreaterRight function having nested iterations which has a worst-case time complexity of $O(n^2)$ .

Space complexity

The space complexity is $O(1)$ . The code maintains a constant space complexity by utilizing a fixed amount of memory irrespective of the size of the input.

Reversing the linked list

The reverse approach is an optimized solution to the problem. Instead of comparing each node with subsequent nodes, we reverse the linked list and iterate through it in reverse order. By doing so, we can track the maximum value seen so far while traversing the reversed list. Nodes with values greater than the maximum value are deleted.

Algorithm

Here’s how the algorithm works:

Reverse the linked list using the standard reversal technique.
Traverse the reversed list from left to right.
Maintain a variable to store the maximum value encountered.
Delete the node if the current node’s value is less than the maximum value.
Update the maximum value if the current node’s value is greater than the maximum value.
Reverse the linked list back to its original order (optional).

To reverse a linked list efficiently, read this short article: How to reverse a linked list in place.

Implementation

Below is the implementation of the algorithm in C++ and Python:

#include <iostream>
class Node {
public:
    int value;
    Node* next;
    Node(int value) {
        this->value = value;
        next = nullptr;
    }
};
class LinkedList {
private:
    Node* head;
public:
    LinkedList() {
        head = nullptr;
    }
    // Add a node at the beginning of the linked list
    void addNode(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }
    // Print the values of all nodes in the linked list
    void printList() {
        Node* currentNode = head;
        while (currentNode) {
            std::cout << currentNode->value << " ";
            currentNode = currentNode->next;
        }
        std::cout << std::endl;
    }
    // Reverse the linked list
    void reverseList() {
        Node* prevNode = nullptr;
        Node* currentNode = head;
        while (currentNode) {
            Node* nextNode = currentNode->next;
            currentNode->next = prevNode;
            prevNode = currentNode;
            currentNode = nextNode;
        }
        head = prevNode;
    }
    // Delete nodes with values greater than the values to their right
    void deleteGreaterRight() {
        reverseList();  // Reverse the linked list to facilitate deletion from right
        int maxValue = head->value;  // Track the maximum value encountered
        Node* currentNode = head->next;
        Node* prevNode = head;  // Keep track of the previous node
        while (currentNode) {
            if (currentNode->value < maxValue) {
                // Remove the currentNode by adjusting the next pointers
                prevNode->next = currentNode->next;
                delete currentNode;
                currentNode = prevNode->next;
            } else {
                // Update the maximum value and move to the next node
                maxValue = currentNode->value;
                prevNode = currentNode;
                currentNode = currentNode->next;
            }
        }
        reverseList();  // Reverse the linked list again to restore the original order
    }
};
int main() {
    LinkedList linkedList;
    linkedList.addNode(10);
    linkedList.addNode(5);
    linkedList.addNode(15);
    linkedList.addNode(9);
    linkedList.addNode(4);
    std::cout << "Given Linked List is:" << std::endl;
    linkedList.printList();
    std::cout << std::endl;
    linkedList.deleteGreaterRight();
    std::cout << "Linked list after deleting nodes is:" << std::endl;
    linkedList.printList();
    return 0;
}

Implementation of the reversing linked list approach in C++

Explanation

Lines 1–14: This is the definition of the Node class, it defines a node with an integer value and a pointer to the next node.
Lines 14–21: The LinkedList class is defined. It has a constructor that initializes the head pointer to nullptr.
Lines 24–28: The addNode function adds a new node to the beginning of the linked list by creating a new node with the given value and updating the head pointer.
Lines 31–38: The printList function prints the values of all nodes in the linked list.
Lines 41–53: The reverseList method reverses the linked list by iteratively updating the next pointer of each node to point to the previous node and updating the head to the last node encountered.
Lines 56–79: The deleteGreaterRight method reverses the linked list. It iterates through the nodes while tracking the maximum value encountered and deletes nodes with lesser values. It then reverses the list again to restore the original order.
Lines 81–99: This is the main function. It creates a LinkedList object and adds several nodes to it. It then prints the initial list, calls the deleteGreaterRight function to modify the list, and finally prints the modified list.

Time complexity

The time complexity is $O(n)$ . The time complexity of the code is $O(n)$ because the most time-consuming operation is the iteration over the linked list.

Space complexity

The space complexity is $O(1)$ . The space complexity of the code is $O(1)$ because it only uses a constant amount of memory, regardless of the input size.

Conclusion

While the brute force approach involves comparing each node with subsequent nodes, the reverse approach provides an optimized solution by reversing the list and tracking the maximum value.

Additional resources

To strengthen your skills in data structures, consider the C++ course on "Data Structures for Coding Interviews." This course focuses on essential data structures and algorithms frequently tested in technical interviews, offering hands-on practice and in-depth explanations. It’s an excellent way to build a solid foundation for tackling coding interview questions and understanding complex data structures, including circular linked lists.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What are the two approaches to solving this problem?

The two primary approaches to solving this problem are as follows:

Brute force approach: Iterate through the list, comparing each node to every node to its right. If any right-side node has a greater value, delete the current node. This approach has a time complexity of $O(n^2)$ .
Optimized approach (reversal technique): Reverse the linked list, then traverse the list from the new head while tracking the maximum value encountered. Delete nodes with values smaller than the current maximum. This improves the time complexity to $O(n)$ .

How does the optimized approach improve performance?

The optimized approach improves performance by reversing the linked list first. By traversing the reversed list and keeping track of the maximum value encountered so far, we can efficiently delete nodes with values smaller than the maximum without needing to compare every node to every other node. This reduces the time complexity to $O(n)$ and maintains $O(1)$ space complexity.

How to remove odd position nodes in a linked list?

Traverse the linked list with two pointers: current and prev. For every odd index, set prev.next to current.next to remove the node. Continue traversing the list and updating pointers accordingly.

How to delete a specific node in a linked list?

If the node to delete is the head, return head.next. Otherwise, traverse the list and find the node with the target value. Update the next pointer of the previous node to skip the node to be deleted.

Why use the reversing approach over brute force?

The reversing approach is more efficient than brute force as it reduces time complexity from $O(n^2)$ to $O(n)$ . It processes each node exactly once, making it ideal for larger inputs. The approach also uses simpler logic, leading to cleaner and more maintainable code. Unlike brute force, it avoids redundant computations and unnecessary nested iterations.

How does the algorithm handle linked lists with duplicate values?

For duplicate values, the algorithm does not treat them as special cases. As long as a node has a greater value later in the list (whether it’s a duplicate or not), it will be deleted. For example, in the list [12, 15, 12, 10], the first 12 would be deleted because 15 is on its right, and the second 12 would not be deleted if no larger value exists on its right.

What happens in distributed linked list scenarios?

In distributed linked list scenarios, nodes may be stored across multiple systems, leading to challenges in synchronization and consistency. Delayed updates, such as latency in propagating changes across nodes, can cause inconsistencies like outdated or missing data during traversal. To mitigate these issues, consensus mechanisms or distributed locks can be used, but they may increase complexity and affect performance.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources