Remove Nodes From Linked List

class Solution {
private:
    ListNode* invertLinkedList(ListNode* startNode) {
        ListNode* previous = nullptr;
        ListNode* current = startNode;
        ListNode* upcoming = nullptr;
    
        while (current != nullptr) {
            upcoming = current->next;
            current->next = previous;
            previous = current;
            current = upcoming;
        }
            
        return previous;
    }
public:
    ListNode* filterNodes(ListNode* head) {
        head = invertLinkedList(head);
    
        int highestValue = 0;
        ListNode* prevNode = nullptr;
        ListNode* currentNode = head;
    
        while (currentNode != nullptr) {
            highestValue = max(highestValue, currentNode->val);
    
            if (currentNode->val < highestValue) {
                prevNode->next = currentNode->next;
                ListNode* nodeToRemove = currentNode;
                currentNode = currentNode->next;
                nodeToRemove->next = nullptr;
            } else {
                prevNode = currentNode;
                currentNode = currentNode->next;
            }
        }
            
        return invertLinkedList(head);
    }
};

This solution involves manipulating a singly linked list to remove certain nodes based on their values. The C++ code comprises a class Solution with private and public member functions designed to perform specific tasks on the linked list.

• Private Function - invertLinkedList

  • Takes a ListNode* representing the start of the list.
  • Inverts the order of nodes in the linked list.
  • Utilizes three pointers (previous, current, and upcoming) to reverse the links between nodes.
  • Returns the new head of the inverted list.

• Public Function - filterNodes

  • Takes the head of the linked list as input.
  • Initially, calls invertLinkedList to reverse the list.
  • Iterates through the reversed list to filter out nodes.
  • Maintains a variable highestValue to store the highest value encountered so far.
  • As it iterates, it compares the value of the current node against highestValue.
  • If the current node's value is less than highestValue, it is removed from the list.
  • The process uses two pointers (prevNode and currentNode) to track and unlink nodes that do not meet the condition.
  • After filtering, the list is inverted again to restore the original order but with specified nodes removed.
  • Returns the head of the modified list.

Ensure that all nodes and memory are handled correctly to prevent memory leaks, particularly when nodes are unlinked and removed from the list. This approach allows retaining only the nodes that hold the highest value from their position to the end of the list at the time they are encountered, thereby ensuring each node in the final list is the maximum from that point onwards, in the original, non-reversed list.

class Solution {
    private ListNode reverseLinkedList(ListNode node) {
        ListNode previous = null;
        ListNode current = node;
        ListNode temporary;
    
        // Reverse the pointers in the linked list
        while (current != null) {
            temporary = current.next;
            current.next = previous;
            previous = current;
            current = temporary;
        }
    
        return previous;
    }
    
    public ListNode removeNodes(ListNode node) {
        // Reversing the linked list initially
        node = reverseLinkedList(node);
    
        int maxVal = 0;
        ListNode prevNode = null;
        ListNode currentNode = node;
    
        // Process each node to remove certain nodes
        while (currentNode != null) {
            maxVal = Math.max(maxVal, currentNode.val);
    
            // Remove nodes smaller than the current maximum
            if (currentNode.val < maxVal) {
                // Skip the current node effectively deleting it
                prevNode.next = currentNode.next;
                ListNode nodeToDelete = currentNode;
                currentNode = currentNode.next;
                nodeToDelete.next = null; // Clear next pointer
            } else {
                prevNode = currentNode;
                currentNode = currentNode.next;
            }
        }
            
        // Return the list after reversing it back to original order
        return reverseLinkedList(node);
    }
}

This Java solution tackles the problem of removing certain nodes from a linked list based on specific conditions. The implementation consists of two major operations:

• In the reverseLinkedList(ListNode node) method, the linked list is reversed. This involves iteratively changing the next pointers of the list nodes, until the list is completely reversed.

• The removeNodes(ListNode node) method first reverses the list using reverseLinkedList(node). It then iterates over the reversed list, maintaining a reference to the maximum value encountered so far (maxVal). As it progresses, it checks each node's value: if a node's value is less than maxVal, that node is skipped (effectively removed from the list). After processing all nodes, the list is reversed again to restore the original order before the nodes were removed.

The core steps involved are:

1. Reverse the input linked list.
2. Traverse the reversed list, removing nodes based on the comparison with maxVal.
3. Reverse the list again to restore the original ordering of nodes.

This solution efficiently filters out nodes without creating a separate data structure, utilizing the reversed list as a way to simplify the conditions for removal based on maximum value logic. After filtering, the reverse operation restores the list to its intended order.

class Solution:
    def invert_linked_list(self, node):
        previous = None
        active_node = node
        temporary_next = None
    
        # Reversing the node links
        while active_node:
            temporary_next = active_node.next
            active_node.next = previous
            previous = active_node
            active_node = temporary_next
    
        return previous
    
    def filter_list(self, node: Optional[ListNode]) -> Optional[ListNode]:
        # Start by flipping the list
        node = self.invert_linked_list(node)
    
        peak_value = 0
        prior = None
        current = node
    
        # Filtering nodes based on the max value seen
        while current:
            peak_value = max(peak_value, current.val)
    
            if current.val < peak_value:
                # Skip the node if smaller than the maximum observed
                prior.next = current.next
                to_be_removed = current
                current = current.next
                to_be_removed.next = None
            else:
                # No need for removal
                prior = current
                current = current.next
    
        # Return the altered list after re-inversion
        return self.invert_linked_list(node)

The "Remove Nodes From Linked List" Python program modifies a singly linked list by removing specific nodes based on a defined condition. The code leverages a two-stage process involving inversion, evaluation, and selective removal of nodes.

• The first method, invert_linked_list, takes a linked list's head node as an input and reverses the list by reassigning next pointers. This method is essential for ensuring that only the maximum values from the original order are preserved when scanning from the back to the front of the list.

• The second method, filter_list, first inverts the linked list. It then iterates through this reversed list, keeping track of the highest value observed so far. During traversal, if a node's value is less than the maximum observed value, it is removed. Nodes are only retained if their value is equal to the maximum value seen up to that point. After the iteration, the list is inverted again to restore the original order, albeit modified.

By inverting the list, comparing node values, and selectively removing nodes, the list is effectively modified so that it keeps only nodes with peak values in their original traversal direction, ensuring no node in the output has a higher node value succeeding it in the list. This methodology guarantees efficiency and correctness in modifying the linked list as per the specified conditions.