Solution For Remove Nodes From Linked List

Problem statement:

Given the head of a linked list, remove all nodes that have a value greater than or equal to the given value threshold.

Example:

Input: head = [4,2,1,3], threshold = 3

Output: [2,1]

Explanation:

Initially, the linked list looks like [4 -> 2 -> 1 -> 3]. Since the threshold is 3, we need to remove all nodes with a value greater than or equal to 3. Therefore, the resulting linked list will be [2 -> 1].

Solution:

The problem statement asks us to remove all nodes from the linked list whose value is greater than or equal to the given threshold. We can solve this problem in a straightforward manner by traversing the linked list and checking each node’s value against the threshold. If a node’s value is greater than or equal to the threshold, we need to remove it from the linked list.

Algorithm:

1. Initialize a pointer prev to null and another pointer current to the head of the linked list.
2. Traverse the linked list until the current pointer is not null.
3. Check if the value of the current node is greater than or equal to the given threshold.
4. If it is greater than or equal to the threshold, we need to remove it from the linked list.
5. If it is not greater than or equal to the threshold, we can move on to the next node by updating the prev pointer to the current node and the current pointer to the next node.
6. If the current node needs to be removed from the linked list, we will update the pointers accordingly. If the current node is the head of the linked list, we will update the head pointer to point to the next node. Otherwise, we will update the prev node’s next pointer to skip the current node and point directly to the next node.
7. Repeat steps 3-6 until the end of the linked list is reached.
8. Return the head of the modified linked list.

Code:

ListNode removeNodes(ListNode head, int threshold) {
ListNode prev = nullptr;
ListNode current = head;

while (current != nullptr) {
    if (current->val >= threshold) {
        if (prev == nullptr) {
            head = current->next;
        } else {
            prev->next = current->next;
        }
    } else {
        prev = current;
    }
    current = current->next;
}

return head;

}

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the linked list. We need to traverse the entire linked list once to remove all nodes that have a value greater than or equal to the threshold.

Space Complexity:

The space complexity of this solution is O(1). We are not using any extra space apart from the two pointers that we initialize in the beginning.

Step by Step Implementation For Remove Nodes From Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        //create a dummy node to avoid corner cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        //initialize first and second pointers
        ListNode first = dummy;
        ListNode second = dummy;
        
        //advance first pointer so that the gap between first and second is n nodes apart
        for(int i=1; i<=n+1; i++){
            first = first.next;
        }
        
        //move first and second pointers until first hits the end of the list
        while(first != null){
            first = first.next;
            second = second.next;
        }
        
        //skip the desired node
        second.next = second.next.next;
        
        //since dummy node is never removed, we can simply return its next node
        return dummy.next;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: ListNode, threshold: int) -> ListNode:
        
        # Set current node to head
        curr = head 
        
        # Set previous node to None
        prev = None
        
        # While current node exists
        while curr:
            
            # Set node_sum to the sum of the current node's value and all values after it
            node_sum = curr.val 
            node = curr.next
            
            # While node exists
            while node:
                
                # Add node's value to node_sum
                node_sum += node.val
                
                # Set node to the next node
                node = node.next
                
            # If node_sum is greater than the threshold
            if node_sum > threshold:
                
                # If the current node is the head
                if curr == head:
                    
                    # Set head to the next node
                    head = curr.next
                    
                    # Set current node to the new head
                    curr = head
                    
                # If the current node is not the head
                else:
                    
                    # Set the previous node's next pointer to the current node's next pointer
                    prev.next = curr.next
                    
                    # Set current node to the new node
                    curr = prev.next
                    
            # If node_sum is not greater than the threshold
            else:
                
                # Set previous node to the current node
                prev = curr
                
                # Set current node to the next node
                curr = curr.next
                
        # Return head
        return head

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} low
 * @param {number} high
 * @return {ListNode}
 */
var removeNodes = function(head, low, high) {
    // base case
    if (!head) return null;
    
    // keep track of current and previous nodes
    let curr = head;
    let prev = null;
    
    // iterate through list
    while (curr) {
        // if node is out of bounds, remove it
        if (curr.val < low || curr.val > high) {
            // if node is head, set head to next node
            if (!prev) {
                head = curr.next;
            } else { // otherwise, skip over node
                prev.next = curr.next;
            }
        } else { // otherwise, update previous node
            prev = curr;
        }
        
        // move to next node
        curr = curr.next;
    }
    
    return head;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }
        while (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNodes(ListNode list, int x) {
        // Create dummy head
        ListNode dummyHead = new ListNode();
        dummyHead.next = list;
        
        // Keep track of previous node
        ListNode prev = dummyHead;
        
        // Iterate through list
        while (list != null) {
            // If current node's value is greater than x
            if (list.val > x) {
                // Remove current node by linking previous node to next node
                prev.next = list.next;
            } else {
                // Otherwise, update previous node to be current node
                prev = list;
            }
            
            // Move to next node
            list = list.next;
        }
        
        // Return dummy head's next node (which is the new head of the list)
        return dummyHead.next;
    }
}