Taro Logo

Remove Nodes From Linked List

#480 Most AskedMedium
Topics:
Linked ListsRecursion

You are given the head of a linked list.

Remove every node which has a node with a greater value anywhere to the right side of it.

Return the head of the modified linked list.

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

Constraints:

  • The number of the nodes in the given list is in the range [1, 105].
  • 1 <= Node.val <= 105

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the data type of the node values in the linked list, and is there a defined range for these values? Can the list contain duplicate node values?
  2. Can the input linked list be empty or contain only a single node?
  3. If all nodes in the linked list need to be removed based on the specified criteria, should I return an empty linked list (null head), or is there a specific sentinel node I should return?
  4. What is the criteria for removing a node? Is it based on the node's value, its position in the list, or some other property? Can you give a detailed example of the removal criteria?
  5. Is the linked list singly or doubly linked? This will affect how I handle node removal.

Brute Force Solution

Approach

The brute force way to remove nodes from a linked list involves checking every possible combination of nodes to remove. This means we'll explore each possible sublist, deciding for each node whether to keep it or delete it, and then checking if the remaining list meets our requirements.

Here's how the algorithm would work step-by-step:

  1. Start by considering keeping all nodes in the list. This is one possible result.
  2. Next, consider removing just the first node and keeping the rest. Check if this new list meets the requirements.
  3. Then, consider removing the second node and keeping the rest. Check if this new list meets the requirements.
  4. Continue this process of removing just one node at a time, each time checking if the list meets the requirements.
  5. Now, consider removing two nodes. Start by removing the first two nodes, then the first and third, and so on, trying every possible pair of nodes to remove.
  6. Again, after removing each pair, check if the remaining list is valid.
  7. Continue this process, increasing the number of nodes being removed at a time (three, four, and so on) and checking if the remaining list meets requirements each time.
  8. Eventually, you'll have considered every possible sublist that could result from removing nodes.
  9. Finally, from all of the valid lists you found (those that meet the requirements), choose the 'best' one according to whatever criteria were specified in the original problem. For example, we might want the longest valid list, or the one that minimizes the sum of the remaining node values.

Code Implementation

def remove_nodes_brute_force(head, requirement_function, comparison_function):
    all_possible_sublists = []

    def generate_sublists(current_node, current_sublist):
        if current_node is None:
            all_possible_sublists.append(current_sublist)
            return

        # Explore the possibility of excluding
        # current node from the sublist.
        generate_sublists(current_node.next, current_sublist.copy())

        # Explore the possibility of including
        # current node in the sublist.
        current_sublist.append(current_node.val)
        generate_sublists(current_node.next, current_sublist.copy())

    generate_sublists(head, [])

    valid_sublists = []
    for sublist in all_possible_sublists:
        # We convert the list of values to a linked list.
        # It is convenient for the later requirement check.
        dummy_head = ListNode(0)
        current = dummy_head
        for value in sublist:
            current.next = ListNode(value)
            current = current.next
        list_head = dummy_head.next

        if requirement_function(list_head):
            valid_sublists.append(sublist)

    best_sublist = None
    for sublist in valid_sublists:
        # Choose the 'best' valid sublist based on
        # the provided comparison function
        if best_sublist is None:
            best_sublist = sublist
        elif comparison_function(sublist, best_sublist):
            best_sublist = sublist

    if best_sublist is None:
        return None

    # We convert the best sublist to a linked list.
    dummy_head = ListNode(0)
    current = dummy_head
    for value in best_sublist:
        current.next = ListNode(value)
        current = current.next

    return dummy_head.next

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Big(O) Analysis

Time Complexity
O(2^n)The brute force approach considers all possible sublists of the linked list. For each node in the linked list of size n, we have two choices: either include it or exclude it. This results in 2 * 2 * ... * 2 (n times) possible sublists to consider. For each of these 2^n sublists, checking if it meets the requirements takes O(n) time in the worst case. Therefore, the total time complexity is O(n * 2^n). Since 2^n dominates n, the overall time complexity is O(2^n).
Space Complexity
O(2^N)The described brute force approach explores every possible sublist by considering each node for inclusion or exclusion. This implicitly requires storing up to 2^N sublists in the worst case. Additionally, for each sublist, the algorithm checks if it meets the requirements, potentially involving creation of a new list. Therefore, in the worst-case scenario where N is the number of nodes in the linked list, the space complexity is O(2^N).

Optimal Solution

Approach

The key to efficiently removing nodes from a linked list lies in traversing the list and making on-the-spot decisions. Instead of revisiting nodes, we'll maintain knowledge of the maximum value encountered so far to determine which nodes need removal as we go. This prevents extra work and makes the process much faster.

Here's how the algorithm would work step-by-step:

  1. Start at the beginning of the linked list.
  2. Keep track of the largest value you've seen so far as you move through the list.
  3. For each node, check if its value is smaller than the largest value you've seen so far.
  4. If the current node's value is smaller, remove it from the list.
  5. If the current node's value is larger or equal to the largest value seen so far, update the largest value to the current node's value and keep it in the list.
  6. Continue doing this until you reach the end of the list.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_nodes(head):
    if not head:
        return None

    maximum_value_so_far = head.value
    current_node = head.next_node
    previous_node = head

    while current_node:
        if current_node.value < maximum_value_so_far:
            # Remove the current node by updating the previous node's next.
            previous_node.next_node = current_node.next_node

        else:
            # Update the maximum value because we found a larger value
            maximum_value_so_far = current_node.value
            previous_node = current_node

        current_node = current_node.next_node

    # Check if the head node needs to be removed
    if head.value < 0:
        return head.next_node
    else:
        return head

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the linked list once, examining each of the n nodes. For each node, a constant amount of work is performed: comparing the node's value to the current maximum and potentially updating the linked list's structure (removing the node or updating the maximum). Since the work done per node is constant and we visit each node once, the time complexity is directly proportional to the number of nodes, resulting in a linear time complexity of O(n).
Space Complexity
O(1)The provided algorithm maintains only a single variable to store the maximum value encountered so far. No additional data structures like arrays, hash maps, or trees are created. Therefore, the auxiliary space required remains constant regardless of the size of the linked list (N), leading to a space complexity of O(1).

Edge Cases

Null or Empty Linked List Input
How to Handle:
Return null immediately; no nodes to process.
All nodes have values to be removed
How to Handle:
The list should become empty after processing; correctly handle head changes.
No nodes need to be removed
How to Handle:
The original list should be returned without modifications; verify no accidental changes.
Consecutive nodes need to be removed
How to Handle:
Properly link the remaining nodes after removing the consecutive nodes.
The head node needs to be removed
How to Handle:
Update the head pointer correctly; handle cases where the new head also needs removal.
Linked list with a single node
How to Handle:
Check if the single node needs removal, and return null if so, otherwise the original list.
Large linked list (potential memory/performance issues)
How to Handle:
Iterative approach avoids stack overflow issues associated with recursion.
All node values are the same
How to Handle:
The algorithm should correctly identify and remove the nodes based on the given criteria, even if the values are identical.
0/1037 completed