Linked list recursive reverse

Posted by Phoenix on Stack Overflow See other posts from Stack Overflow or by Phoenix
Published on 2010-03-12T17:05:10Z Indexed on 2010/03/12 17:07 UTC
Read the original article Hit count: 402

Filed under:
|
|
|

I was looking at the code below from stanford library:

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;  

    /* put the first element on the end of the list */
    recursiveReverse(&rest);
    first->next->next  = first; 

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

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

What I don't understand is in the last recursive step for e.g if list is 1-2-3-4 Now for the last recursive step first will be 1 and rest will be 2. So if you set *head_ref = rest .. that makes the head of the list 2 ?? Can someone please explain how after reversing the head of the list becomes 4 ??

© Stack Overflow or respective owner

Related posts about linked-list

Related posts about recursion