Delete Below Threshold

Difficulty: ⚫⚫◯◯

Tags: linked-list, deletion, free, memory

Hurdle: Passing this question is sufficient to pass the linked lists hurdle.

Description

Write a function delete_below_threshold that is given two arguments:

• head: a pointer to the first node in a linked list
• threshold: an integer value

The function should delete all nodes whose data value is less than the threshold value.

Important:

• Nodes with data equal to the threshold should NOT be deleted (only strictly less than).
• The head may change if the first node(s) are deleted!
• You must call free() to free the memory for each deleted node.

The function should return a pointer to the head of the modified list.

Examples

Example 1

Input:  threshold=4, list: 3 -> 7 -> 2 -> 8 -> 1 -> 5 -> X
Output: 7 -> 8 -> 5 -> X

Explanation: Nodes 3, 2, and 1 were removed because they are less than 4.

Example 2

Input:  threshold=5, list: 1 -> 2 -> 3 -> 8 -> 9 -> X
Output: 8 -> 9 -> X

Explanation: Nodes 1, 2, and 3 were removed because they are less than 5.

Example 3

Input:  threshold=10, list: 1 -> 2 -> 3 -> 4 -> 5 -> X
Output: (empty)

Explanation: All nodes are less than 10, so all are removed.

Example 4

Input:  threshold=0, list: 1 -> 2 -> 3 -> 4 -> 5 -> X
Output: 1 -> 2 -> 3 -> 4 -> 5 -> X

Explanation: No nodes are less than 0, so none are removed.

Example 5: Negative Numbers

Input:  threshold=0, list: -3 -> 5 -> -1 -> 8 -> -2 -> 3 -> X
Output: 5 -> 8 -> 3 -> X

Explanation: Negative numbers are less than 0, so they are removed.

Example 6: Equal to Threshold

Input:  threshold=5, list: 3 -> 5 -> 7 -> X
Output: 5 -> 7 -> X

Explanation: Node 3 is removed (3 < 5). Node 5 is kept (5 is NOT less than 5).

Example 7: Empty List

Input:  threshold=5, list: (empty)
Output: (empty)

Example 8: Single Node Kept

Input:  threshold=5, list: 10 -> X
Output: 10 -> X

Example 9: Single Node Removed

Input:  threshold=5, list: 3 -> X
Output: (empty)

Function Signature

struct node *delete_below_threshold(struct node *head, int threshold);

Data Structure

struct node {
    struct node *next;
    int          data;
};

Constraints

• You can assume a value will always be given for threshold.
• The list may be empty.
• The list may contain negative numbers.
• Nodes with data equal to the threshold should NOT be deleted.
• You must call free() for each deleted node.
• Do not change the data fields of list nodes.
• Do not use arrays.
• Do not call malloc.
• Do not call scanf, getchar, or fgets.
• Do not call printf.

Hints

• Handle the case where the head itself needs to be deleted.
• Use a loop to skip over leading nodes that should be deleted.
• For nodes in the middle, track the previous node so you can update its next pointer.
• Always free() deleted nodes to avoid memory leaks.

Testing

The first argument is the threshold, remaining arguments form the linked list.

./delete-below-threshold 4 3 7 2 8 1 5
[7, 8, 5]

./delete-below-threshold 5 1 2 3 8 9
[8, 9]

./delete-below-threshold 10 1 2 3 4 5
[]

./delete-below-threshold 0 1 2 3 4 5
[1, 2, 3, 4, 5]

./delete-below-threshold 0 -3 5 -1 8 -2 3
[5, 8, 3]

./delete-below-threshold 5 3 5 7
[5, 7]

./delete-below-threshold 5
[]

./delete-below-threshold 5 10
[10]

./delete-below-threshold 5 3
[]