[GFG] delete nodes having greater value on right

mail@pastecode.io avatarunknown
c_cpp
a month ago
931 B
7
Indexable
Never
// AMAN JAIN MCA 1st YEAR 2nd SEM

// time O(N), space O(N)
// Approach: Use recursion to traverse linked list in reverse and
// keep note of largest element encountered till now. If the current
// element is smaller than the largest element encountered till now, 
// then remove that node otherwise update the largest element
class Solution {
public:
    
    Node* updateList(Node* head, int& currentLargest) {
        if(head == NULL) {
            return NULL;
        }
        Node* new_next = updateList(head -> next, currentLargest);
        if(head->data < currentLargest) {
            return new_next;
        }
        else {
            currentLargest = head -> data;
            head -> next = new_next;
            return head;
        }
    }
    
    Node *compute(Node *head) {
        int currentLargest = INT_MIN;
        Node* new_head = updateList(head, currentLargest);
        return new_head;
    }
    
};