CODEWITHSUNDEEP
crecursionlinked-listsingly-linked-listfunction-definition
mrreaper72
mrreaper72

Reputation: 87

trying to understand this recursion

I need to take a linked list and return a mirror version of it, here is an example

input: 1->2->3->4->5->null.

result: 1->2->3->4->5->5->4->3->2->1->NULL.

I have to visit each node once only

I managed to solve it but I really cant understand the solution so can anyone help me break down the mirror function?

my code:

#include <stdio.h>
#include <stdlib.h>

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

} node;


void PushEnd(node** headRef, int data)

{
    node* newnode = malloc(sizeof(node));

    if (!newnode)
        return;

    newnode->data = data;

    if (*headRef == NULL)
        {
            newnode->next = NULL;
            *headRef = newnode;
        }
    else
        {
            node* current = *headRef;
            node* prev;
            while (current->next)
                {
                    current = current->next;
                }
            current->next = newnode;
            newnode->next = NULL;
        }
}


void printList(node* head)
{
    if (head == NULL)
        return;
    printf("%d ", head->data);

    printList(head->next);
}
node* mirror(node* head)
{
    node* new = NULL;
     
    if (head == NULL)
        return NULL;
    
    PushEnd(&new,head->data);
    
    new->next=mirror(head->next);
   PushEnd(&new, head->data); 
    return new;
}
void Test()
{
    node* head = NULL;
    
    int a[] = {10,50,19,54,30};
    for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
        {
            PushEnd(&head, a[i]);
            
        }
    printList(head);
    printf("\n");
    node* new = mirror(head);
    printList(new);
}
int main()
{
    Test();
    return 0;
}

using this call : new->next=mirror(head->next); how does it push the first element?

thanks in advance

Upvotes: 1

Views: 56

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 311068

In the first call of the function the pointer new is equal to NULL. Then the function PushEnd is called.

PushEnd(&new,head->data);

So now the result list looks like (if to use data from your array)

| 10 | NULL |
     ^
     |
    new

Then the function calls recursively itself ( for example for the array element with the value 50)

new->next=mirror(head->next);

After exit from this call and due to the assignment to the pointer new->next in the statement above you will have

| 10 | ->50 | -> | 50 | ...| -> ... | ...| NULL|
     ^
     |
    new

Now the value 10 is appended to the tail of the list

PushEnd(&new, head->data);

and you will have

| 10 | ->50 | -> | 50 | ...| -> ... | ...| ->10 | -> | 10 | NULL |
     ^
     |
    new

This approach is inefficient due to the call of the function PushEnd because it needs to traverse the whole new built list to achieve its tail.

Upvotes: 1

Related Questions