# 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:

- Initialize a pointer prev to null and another pointer current to the head of the linked list.
- Traverse the linked list until the current pointer is not null.
- Check if the value of the current node is greater than or equal to the given threshold.
- If it is greater than or equal to the threshold, we need to remove it from the linked list.
- 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.
- 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.
- Repeat steps 3-6 until the end of the linked list is reached.
- 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; } }