Delete Nth Even

Difficulty: ⚫⚫◯◯

Tags: linked-list, deletion, traversal

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

Description

Write a function delete_nth_even that is given two arguments: head (a pointer to the first node in a linked list) and n (the position of the even node to delete, counting only nodes with even values).

The function should delete the nth node in the list that contains an even number, counting only the nodes with even values from the start of the list.

Special Cases:

• If n is greater than the number of even nodes in the list, delete the first even node instead.
• If the list contains no even numbers, do not delete any nodes and leave the list unchanged.

The function should:

• Return a pointer to the head of the list (which may have changed)
• Free the memory of the deleted node

Examples

Example 1

Input:  n=2, list: 4 -> 3 -> 7 -> 2 -> 35 -> 4 -> 3 -> X
Output: 4 -> 3 -> 7 -> 35 -> 4 -> 3 -> X

Explanation: The even nodes are 4 (1st), 2 (2nd), 4 (3rd). The 2nd even node (value 2) is deleted.

Example 2

Input:  n=1, list: 2 -> 3 -> 4 -> X
Output: 3 -> 4 -> X

Explanation: The 1st even node (value 2) is deleted. This was the head, so the new head is 3.

Example 3

Input:  n=9, list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> X
Output: 1 -> 3 -> 4 -> 5 -> 6 -> X

Explanation: There are only 3 even nodes (2, 4, 6), but n=9. Since n exceeds the count, delete the 1st even node (value 2).

Example 4

Input:  n=1, list: 1 -> X
Output: 1 -> X

Explanation: No even numbers in the list, so nothing is deleted.

Example 5

Input:  n=11, list: 1 -> 3 -> 5 -> 7 -> 9 -> X
Output: 1 -> 3 -> 5 -> 7 -> 9 -> X

Explanation: No even numbers in the list, so nothing is deleted.

Function Signature

struct node *delete_nth_even(struct node *head, int n);

Data Structure

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

Constraints

• You can assume n will always be 1 or greater.
• You cannot assume the list is non-empty.
• If there are no even numbers, do not delete any nodes.
• delete_nth_even should return the (possibly changed) head of the list.
• delete_nth_even must call free() to free the deleted node's memory.
• 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 (the function should only return a value).

Hints

• First, count how many even nodes exist in the list.
• If n is greater than the count of even nodes, set n = 1.
• Be careful when deleting the head node.
• Remember to free the deleted node.

Testing

./delete-nth-even 2 4 3 7 2 35 4 3
[4, 3, 7, 35, 4, 3]

./delete-nth-even 1 2 3 4
[3, 4]

./delete-nth-even 9 1 2 3 4 5 6
[1, 3, 4, 5, 6]

./delete-nth-even 5 10 20 30 40 50
[10, 20, 30, 40]

./delete-nth-even 3 10 20 30 40 50
[10, 20, 40, 50]

./delete-nth-even 1 1
[1]

./delete-nth-even 11 1 3 5 7 9
[1, 3, 5, 7, 9]