Write a recursive function to insert a node in a sorted single kinked list.

Question

How to delete the node that given as argument in single linked list?
Is there any system call to get prev pointer ?

Note: Here the goal is to delete the address not the node's value

Answer 1

void sortedInsert(struct node** head_ref, struct node* new_node)
{
    struct node* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
               current->next->data < new_node->data)
        {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

Comments

This is iterative code but question was about recursive.

Answer 2

You need to find a node after which we can insert

Iterative code

void sortedInsert(struct node** head_ref, struct node* new_node)
{
    struct node* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
               current->next->data < new_node->data)
        {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

Recursive code

void sortedInsertRecursive(struct node **head_ref, struct node* new_node)
{
    struct node* current;
    /* Special case for the head end */
    if ((*head_ref) == NULL || (*head_ref)->data >= new_node->data)
    {
        new_node->next = *head_ref;
        (*head_ref) = new_node; // Its double pointer case so it should correct the parent pointer 
    }
    else
    {
        /* Locate the node before the point of insertion */
        if ((*head_ref)->next != NULL &&
               (*head_ref)->next->data < new_node->data)
        {
            sortedInsertRecursive((*head_ref)->next, new_node);
        }
    }
}