Reversing Linked List using recursion algorithm

Question

I'm having trouble understanding how the algorithm for reversing the linked list fixes the head pointer.

void recursiveReverse(struct node** head_ref)
{
struct node* first;
struct node* rest;

/* empty list */
if (*head_ref == NULL)
   return;   

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

/* List has only one node */
if (rest == NULL)
   return;   

/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next  = first;  

/* tricky step -- see the diagram */
first->next  = NULL;          

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

I understood everything before that, its the last line that I don't get.
If the list is 1->2->3. So, recursiveReverse(2) will set *head_ref as 3. But when it returns to recursiveReverse(1), here rest points to 2. So shouldn't that set *head_ref to 2, (which is incorrect) but it doesn't actually. How does this work?

Remember that in the recursive call the variable head_ref is actually the parameter &rest that you pass in to the recursive call. I suggest that you run in a debugger, and step through the code line by line, and step into each recursive call. For a small list of three or four nodes it's pretty quick and should give you more insight. — Some programmer dude
– Some programmer dude, Commented Aug 29, 2015 at 7:02

Alex Sherman · Accepted Answer · 2015-08-29 07:09:02Z

1

When recursiveReverse(2) is called, recursiveReverse(1) is passing a reference to rest which recursiveReverse(2) modifies to point to 3. Then when recursiveReverse(1) sets *head_ref = rest; rest is actually pointing at 3.

answered Aug 29, 2015 at 7:09

Alex Sherman

5243 silver badges9 bronze badges

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

1 Comment

user270386 Over a year ago

Thanks! This was easier to understand than thinking in pointers and double-pointers.

rcgldr · Accepted Answer · 2015-08-29 20:46:21Z

An alternative explanation. In the code before the recursive call, in the next to last nested call, rest is set to point to the last node, and in the last call, rest is set to the NULL at the end of the list, but in this case the function returns without updating head_ref==rest, so after the second return from recursiveReverse, rest points to the last node, and is never updated again. The "tricky step" isn't that tricky, if it's a nested call, then when recursiveReverse returns, first->next->next will overwrite it. If it's the initial call, then what was the first node's next pointer is set to null. Commented version:

void ReverseList(NODE**a)
{
NODE *list;     /* will be pointer to reversed list */
    /* NULL check */
    if(a == NULL || *a == NULL)
        return;
    /* recurse until last node is reached */
    list = (*a)->next;
    if (!list)
        return;
    ReverseList(&list);
    /* list now points to what was last node */
    /* reverse a next pointer */
    (*a)->next->next = *a;
    /* set current end of reversed list */
    /*  next gets over written if nested call */
    (*a)->next = NULL;
    /* set pointer to start of reversed list */
    *a = list;
}

alternate version that returns a pointer rather than use a double pointer:

NODE * ReverseList(NODE*a)
{
NODE *list;     /* will be pointer to reversed list */
    /* NULL check */
    if(a == NULL)
        return NULL;
    /* recurse until last node is reached */
    list = a->next;
    if(list == NULL)
        /* return pointer to last node */
        return a;
    list = ReverseList(list);
    /* list now points to what was last node */
    /* reverse a next pointer */
    a->next->next = a;
    /* set current end of reversed list */
    /*  next gets over written if nested call */
    a->next = NULL;
    /* return pointer to what was last node */
    return list;
}

Collectives™ on Stack Overflow

Reversing Linked List using recursion algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related