Remove Nodes From Linked List - Leetcode Solution

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.

1