### Reversing a linked list recursively

Can anybody please explain me why rest always points to the last element (line:
24)? If it is because of variable rest is send as reference (&rest) parameter
recursively, then why it does not point to the NULL? Let's say we have a list
{1,2,3,4}. When the RecursiveReverse(&rest) is called for 4, it is the last
call and rest is set to NULL (see line 9) and recursive call terminates since
rest is NULL. Then why at the end of each call (pop from the stack) it points
to the last element? May be I am missing "what happnes to last activation record" in recursive call?

2 {
3 // Base case
5 return;
6
8
10
11 if(rest == NULL)
12 {
13 return;
14 }
15
16 // Recursive case
17
18 recursiveReverse(&rest);
19
20 first->next->next = first;
21 first->next = NULL;
22
23 // rest always point to the last
25 }
 ``12345678910111213`` ``````void reverse(Node** n) { if ( n == nullptr || (*n)->next == nullptr ) return ; Node * first = *n ; Node * next = *n = first->next ; first->next = nullptr ; reverse( n ) ; next->next = first ; }``````
> When the RecursiveReverse(&rest) is called for 4,
> it is the last call and rest is set to NULL (see line 9)
a local variable `rest' is set to NULL, what you passed as parameter remains unchanged.
the parameter would change in line 24, but that is not reached as you return in 13

Your base case may be done as
 ``12`` ``````if( not *headRef or not (*headRef)->next ) //empty or just one element return;``````

Last edited on
Thank you so much! I just drew the activation record. It makes perfect sense now.
I will update the base case.
Topic archived. No new replies allowed.