Insert Between Diff

Difficulty: ⚫⚫◯◯

Tags: linked-list, insertion, malloc, traversal

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

Description

Write a function insert_between_diff that is given two arguments, value and head, where head is a pointer to the first node in a linked list.

The function should create a new node (using malloc) containing value, and insert it between the first occurrence of two consecutive nodes whose values have an absolute difference of 6 or 7.

The absolute difference between two values a and b, written |a - b|, is always non-negative. For example |1 - 8| is 7, and |3 - 9| is 6.

Special Cases:

If the list is empty, return a pointer to the new node containing value.
If no two consecutive nodes have a difference of 6 or 7, insert the new node at the tail of the list.

The function should return a pointer to the head of the list, which may have changed.

Examples

Example 1

value = 99, list: 1 -> 8 -> 2 -> 3 -> X

Output: 1 -> 99 -> 8 -> 2 -> 3 -> X

Explanation: The first pair with a difference of 6 or 7 is 1 and 8, since |1 - 8| is 7. The value 99 is inserted between them.

Example 2

value = 8, list: 1 -> 3 -> 9 -> 16 -> X

Output: 1 -> 3 -> 8 -> 9 -> 16 -> X

Explanation: |1 - 3| is 2, so the first pair does not match. |3 - 9| is 6, so the value 8 is inserted between 3 and 9. Note that |9 - 16| is 7 and would also match, but it is not the first occurrence.

Example 3

value = 19, list: 1 -> 2 -> 1 -> 2 -> X

Output: 1 -> 2 -> 1 -> 2 -> 19 -> X

Explanation: Every consecutive pair differs by 1, so no pair matches. The new node goes at the tail.

Example 4

value = 9, list: 10 -> 6 -> 1 -> 8 -> X

Output: 10 -> 6 -> 1 -> 9 -> 8 -> X

Explanation: |10 - 6| is 4 and |6 - 1| is 5, so neither matches. |1 - 8| is 7, so 9 is inserted between 1 and 8.

Example 5

value = 3, list: 5 -> X

Output: 5 -> 3 -> X

Explanation: A list with one node has no consecutive pairs at all, so the new node goes at the tail.

Example 6

value = 1, list: 8 -> 1 -> 2 -> 3 -> X

Output: 8 -> 1 -> 1 -> 2 -> 3 -> X

Explanation: |8 - 1| is 7. The pair matches even though the values decrease, because the difference is absolute.

Function Signature

struct node *insert_between_diff(int value, struct node *head);

Data Structure

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

Constraints

You cannot assume the list is non-empty.
The data fields may contain any integer (positive, negative, or zero).
Only the first matching pair should receive the new node.
If no pair matches, the new node must be added at the tail of the list.
insert_between_diff must call malloc to create the new node.
insert_between_diff should return the (possibly changed) head of the list.
Do not change the data fields of the existing list nodes.
Do not use arrays.
Do not call scanf, getchar, or fgets.
Do not call printf (the function should only return a value).

Hints

You may use the abs() function from stdlib.h. Without it, a pair such as 8 followed by 1 will be missed, because 1 - 8 is -7 rather than 7.
Set both fields of your new node before you attach it. Forgetting new_node->next = NULL on the tail path leaves a garbage pointer, and the list may print correctly on one machine and crash on another.
You are comparing pairs, not single nodes. Looping while curr->next != NULL means you always have both curr and curr->next available to compare.
That same loop condition leaves curr sitting on the last node when nothing matched, which is exactly where you need it for the tail insertion.
Inserting after curr is two assignments, and the order matters. Point the new node at curr->next first, then point curr at the new node. Doing it the other way around loses the rest of the list.
Handle the empty list before you touch head->data.

Testing

The first argument is the value to insert. The remaining arguments are the list.

./insert-between-diff 99 1 8 2 3
[1, 99, 8, 2, 3]

./insert-between-diff 9 10 6 1 8
[10, 6, 1, 9, 8]

./insert-between-diff 19 1 2 1 2
[1, 2, 1, 2, 19]

./insert-between-diff 8 1 3 9 16
[1, 3, 8, 9, 16]

./insert-between-diff 3 5
[5, 3]

./insert-between-diff 7
[7]

./insert-between-diff 1 8 1 2 3
[8, 1, 1, 2, 3]

./insert-between-diff 4 1 6 14 22
[1, 6, 14, 22, 4]