Insert Alphabet After

Difficulty: ⚫⚫◯◯

Tags: linked-list, insertion, malloc, alphabet

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

Description

Write a function insert_alphabet_after that is given two arguments:

• ch: a character to insert
• head: a pointer to the first node in a linked list of characters

The function should find every node in the linked list which contains the letter directly before ch in the alphabet. For each such node found, it should create a new node (using malloc) containing ch and insert it after that node.

Special Cases:

• If head is empty (NULL), return a pointer to a new node containing ch.
• If ch is 'a', it should only be added if the list is empty (since no letter comes before 'a').

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

Examples

Example 1

Input:  ch='b', list: a -> X
Output: a -> b -> X

Explanation: 'a' comes directly before 'b' in the alphabet. Insert 'b' after 'a'.

Example 2

Input:  ch='e', list: d -> c -> b -> a -> X
Output: d -> e -> c -> b -> a -> X

Explanation: 'd' comes directly before 'e'. Insert 'e' after 'd'.

Example 3

Input:  ch='a', list: (empty)
Output: a -> X

Explanation: Empty list, so create a new node with 'a'.

Example 4

Input:  ch='a', list: h -> e -> l -> l -> o -> X
Output: h -> e -> l -> l -> o -> X

Explanation: 'a' has no predecessor in the alphabet, and the list is not empty, so nothing is inserted.

Example 5

Input:  ch='e', list: d -> d -> d -> d -> X
Output: d -> e -> d -> e -> d -> e -> d -> e -> X

Explanation: Every 'd' should have an 'e' inserted after it.

Example 6

Input:  ch='b', list: a -> a -> b -> b -> X
Output: a -> b -> a -> b -> b -> b -> X

Explanation: Insert 'b' after every 'a'.

Function Signature

struct node *insert_alphabet_after(char ch, struct node *head);

Data Structure

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

Constraints

• All characters will be lowercase alphabet characters (a-z).
• You cannot assume the list is ordered alphabetically.
• If there are multiple nodes with the character before ch, insert after every one.
• Do not use arrays.
• Do not call scanf, getchar, or fgets.
• Do not call printf (the function should only return a value).
• You must use malloc to create new nodes.

Hints

• The character directly before ch in the alphabet is ch - 1.
• When inserting a node, be careful to update pointers in the correct order.
• After inserting, make sure to advance past the newly inserted node to avoid infinite loops.

Testing

The first argument is the character to insert. The remaining arguments form the linked list.

./insert-alphabet-after b a
[a, b]

./insert-alphabet-after e d c b a
[d, e, c, b, a]

./insert-alphabet-after a
[a]

./insert-alphabet-after a h e l l o
[h, e, l, l, o]

./insert-alphabet-after h
[h]

./insert-alphabet-after b a a b b
[a, b, a, b, b, b]