75.md

Delete nodes having greater value on right

GFG Link

    Node* reverseList(Node* head) {
        Node* prev = nullptr;
        Node* current = head;
        Node* next = nullptr;

        while (current) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

    Node* compute(Node* head) {
        if (!head) return nullptr;

        // Step 1: Reverse the linked list
        head = reverseList(head);

        // Step 2: Filter nodes
        int maxValue = INT_MIN;
        Node* filteredHead = nullptr;
        Node* filteredTail = nullptr;

        Node* current = head;
        while (current) {
            if (current->data >= maxValue) {
                Node* newNode = new Node(current->data);
                if (!filteredHead) {
                    filteredHead = filteredTail = newNode;
                } else {
                    filteredTail->next = newNode;
                    filteredTail = newNode;
                }
                maxValue = current->data;
            }
            current = current->next;
        }

        // Step 3: Reverse the filtered list again to restore the original order
        return reverseList(filteredHead);
    }