Recursively reverse linked list

Question

I am having hard time understanding how this recursive code works, I have made drawings and run the code through gdb.

void RecursiveReverse(struct node** headRef) 
{
  struct node* first;
  struct node* rest;

  if (*headRef == NULL) return; // empty list base case

  first = *headRef; // suppose first = {1, 2, 3}
  rest = first->next; // rest = {2, 3}

  if (rest == NULL) return; // empty rest base case

  RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                           // after: rest = {3, 2}

  first->next->next = first; // put the first element on the end of the list
  first->next = NULL;

  *headRef = rest; // fix the head pointer
}

I understand that while the recursion call stack is being built up and once the list contains only {3}, empty rest base case if (rest == NULL) is true for the first time.

---

After this, the recursion call stack starts to break and hits first->next->next = first; for the first time, with {2, 3},

Before this line is executed, output in gdb:

(gdb)p *first
{data = 2, next = 0x1003001f0}

(gdb) p *rest
{data = 3, next = 0x0} 

After this line is executed,

(gdb) p *rest
{data = 3, next = 0x1003000a0}

---

Continuing with code execution to hit first->next->next = first;, the second time:

(gdb) p **head_ref
{data = 1, next = 0x1003000a0}

(gdb) p *rest
{data = 3, next = 0x1003000a0} // expected p *rest to be 2

Here I expected that the local pointer rest should point to node 2, because while building up recursion call stack, **headRef pointed to node 1 and after line rest = first->next;, got executed rest pointed to node 2.

After *headRef = rest;, is executed, shouldn't headRef point to node 2?

How come that local state is lost and rest points to node 3?

Answer 1

Let's assume that you have a list and its rest part is already reversed.

Before reversing the rest part the list had this structure

first -> first_of_rest -> second_of_rest->...->nth_of_rest->nullptr

After reversing the rest part you will get

first -> nullptr <- first_of_rest <- second_of_rest <-...<-nth_of_rest
         |                                                      |
         ________________________________________________________
                            the rest part of the list

So the data member next of the node first points to first_of_rest while the data member next of the node first_of_rest "points" to nullptr.

So what we need to do at this moment is to set the data member of the node first_of_rest to point to the node first

first->next->next = first;

abd set the data member next of the node first to "point" to nullptr.

first->next = NULL;

Thus we have

nullptr <-first <- first_of_rest <- second_of_rest <-...<-nth_of_rest