Linked list recursion calling by reference in C

Question

I'm practicing with linked lists using C. I'm a beginner programmer just started learning C two weeks ago.

I understand the concept of linked list very well and I was trying to reverse a linked list using recursion.

I know how to reverse it using a while loop, however with the recursion I'm stuck on how to point the head pointer to the last number address instead of the initial first number address after I reverse the list.

Below is my reverse function. The head is defined in main and I'm calling it by reference into my function. I know I can solve the issue by calling it by value and just writing in main() head=reverse(node* head); or by defining head in the dynamic memory and just accessing it straight from the function. I don't want to do that. I want to call it by reference from main and the function to return void.

Here is my reverse function:

void reverse(struct node** head)
{   
    struct node* p=*head;


    if(p->link==NULL)
    {  *head=p;
        return;
    }

    reverse(&(p->link));
    p->link->link=p;
    p->link=NULL;


}

Say The list is: 5 6 7 2 3 4 The output I'm getting after reverse is: 5 I know the reason is because the head is still pointing at the first number address. I cant figure it out how to point it to the last number address. It should have done that in the if statement when it breaks the recursion function. But its not working.

Thank you!

well if you use recursion the way you are specifying and reversing the list the head shouldn't be the head anymore and the tail of the linked list becomes the head... So what used to be the head becomes the tail and what was the tail becomes the head. In order to get the new head you need to access the old tail node — RAZ_Muh_Taz
– RAZ_Muh_Taz, Commented Sep 22, 2016 at 0:11
Yes I know that but how do I return the address of the old tail? Should *head=p; in the if statement be doing that? — Majd Takidin
– Majd Takidin, Commented Sep 22, 2016 at 0:15
How do you return the address of the tail? Well, if you called the function on the last node, return address of that node. Otherwise, think about what you want to do with the address returned by the recursive call. — Beta
– Beta, Commented Sep 22, 2016 at 0:46
The function returns a void, I can't return an address by the recursive call. I meant to say how can I access the address of the original head so I can assign it to the tail? — Majd Takidin
– Majd Takidin, Commented Sep 22, 2016 at 1:10

Douglas · Accepted Answer · 2016-09-22 00:55:16Z

0

The new head node is the old tail. The old tail is known only in the base case, the deepest layer of recursion where there's nothing left to further recurse on. You therefore have two options: make the original head available by reference through the entire call stack so that the base case can reassign it, or return the old tail up the call stack so that it's available at the top level to do the reassignment.

answered Sep 22, 2016 at 0:55

Douglas

5,0971 gold badge17 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Majd Takidin Over a year ago

I know how to solve it using dynamic memory. But I want to understand the recursive function better by knowing how to access the address of the original head so I can assign it to the tail. To my understanding, the address is available at the beginning when its called by reference from main, then its assigned to the pointer p. The function calls itself each time changing the referenced address to the adjacent node till it reaches the tail (NULL). It then breaks the recursion and the recursion unfolds, with each unfolding the addresses are reversed while it goes back to the first node.

Majd Takidin Over a year ago

How can I recover the address of the original head that got lost?

Collectives™ on Stack Overflow

Linked list recursion calling by reference in C

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related