Inserting a node in a linked list using recursion

[zzQwerty]

Can anyone explain how to insert a linked list using recursion? I found this code online, and cannot figure it out.

  struct node *insert(struct node *p, int n)
{
        struct node *temp;
        if(p==NULL)
        {
                p=(struct node *)malloc(sizeof(struct node));
                if(p==NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                p-> data = n;
                p-> link = NULL;
        }
        else
                p->link = insert(p->link,n);/* the while loop replaced by
                                               recursive call */
        return (p);
}

I am coding in c++. What does p=(struct node *)malloc(sizeof(struct node)); do?

[Nico]

To insert a node in a linked list you have to think about what kind of list it is, specifically: is it a sorted list or not?

If it is not sorted:
- check if there is a head node. If not, insert the new node at the head and you are done.
Otherwise start at the head and:
- try to get a pointer to the next node.
- if there is a next node, repeat the same check.
- otherwise, insert the new node at the position of the next node.

If it is a sorted list, you do the same, but you may find a node with a smaller value than the new node, in which case you have to insert the new node between the two current nodes.


p.s. you should not need and maloc should never be used without a corresponding free but: http://www.cplusplus.com/reference/cstdlib/malloc/

[cire]

I am coding in c++.

One wouldn't know it from looking at the code. That appears to be pure, poorly written C.

C++ would probably look something like this:

node* insert(node* p, int n)
{
    if (!p)
        p = new node {n, nullptr}; // order of initializers may need to change.
    else
        p->link = insert(p->link, n);
    
    return p;
}

Or we might even take p by reference:

void insert(node*& p, int n)
{
    if (!p)
        p = new node {n, nullptr}; // order of initializers may need to change.
    else
        insert(p->link, n);
}

[Nico]

The code was found in a dark and possibly forgotten corner of the internet and is therefor not the work of zzQwerty.
zzQwerty is programming in C++, that doesn't say anything about the people that have put this code online.

Although I will agree that it would be more useful to see zzQwerty's attempt to solve the problem, as that would probably provide some insight in what the exact problem is.