Count In Range

Difficulty: ⚫◯◯◯

Tags: linked-list, traversal, counting

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

Description

Write a function count_in_range that is given one argument, head, which is a pointer to the first node of a linked list.

The function should return the count of how many nodes in the list have a value strictly between the value of the first node and the value of the last node.

"Strictly between" means the value must be greater than the first node's value and smaller than the last node's value. A node whose value is equal to either boundary is not counted.

Special Cases:

• If the first node's value is greater than or equal to the last node's value, return 0.
• If the list has fewer than three nodes, return 0, as there are no nodes in a range.
• If the list is empty, return 0.

Examples

Example 1

List: 2 -> 10 -> 5 -> 2 -> 7 -> 12 -> X

Output: 3

Explanation: The first value is 2 and the last value is 12, so we are counting values strictly between 2 and 12. The values 10, 5 and 7 qualify. The middle node with value 2 is equal to the first node's value, so it is not counted.

Example 2

List: 12 -> 10 -> 11 -> 13 -> 14 -> X

Output: 1

Explanation: The first value is 12 and the last value is 14. Only 13 lies strictly between them. The values 10 and 11 are smaller than 12, so they are not counted.

Example 3

List: 5 -> 7 -> 10 -> X

Output: 1

Explanation: The first value is 5 and the last value is 10. Only 7 lies strictly between them.

Example 4

List: 10 -> 2 -> 5 -> 3 -> X

Output: 0

Explanation: The first value is 10 and the last value is 3. Since the first value is greater than the last value, the answer is 0.

Example 5

List: 1 -> 10 -> 1 -> 10 -> 1 -> X

Output: 0

Explanation: The first value is 1 and the last value is also 1. Since the first value is not smaller than the last value, the answer is 0.

Example 6

List: 5 -> 10 -> X

Output: 0

Explanation: The list has fewer than three nodes, so there are no nodes between the first and the last.

Function Signature

int count_in_range(struct node *head);

Data Structure

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

Constraints

• count_in_range should return only a single integer.
• A node whose value equals the first or the last node's value is not counted.
• If the first node's value is greater than or equal to the last node's value, count_in_range should return 0.
• You cannot assume the list is non-empty.
• The data fields may contain any integer (positive, negative, or zero).
• Do not change the linked list provided.
• Do not change the next or data fields of list nodes.
• Do not use arrays.
• Do not call malloc.
• Do not call scanf, getchar, or fgets.
• Do not call printf (the function should only return a value).

Hints

• You need the value of the last node before you can start counting, so walk to the end of the list first.
• Check for an empty list before reading head->data.
• The first and last nodes can never be strictly between themselves, so you can safely test every node in the list.
• Keep the counter outside the loop, and do not stop early when a node fails the test.

Testing

./count-in-range 2 10 5 2 7 12
3

./count-in-range 12 10 11 13 14
1

./count-in-range 5 7 10
1

./count-in-range 10 2 5 3
0

./count-in-range 1 10 1 10 1
0

./count-in-range 10 1 10 1 10
0

./count-in-range 5 10
0

./count-in-range 7
0

./count-in-range
0