A single statement Confusing Recursive Solution Anybody Help!!!

  • 0
    void recursiveReverse(struct node** head_ref)
        struct node* first;
        struct node* rest;
        /* empty list */
        if (*head_ref == NULL)
        /* suppose first = {1, 2, 3}, rest = {2, 3} */
        first = *head_ref;  
        rest  = first->next;
        /* List has only one node */
        if (rest == NULL)
        /* reverse the rest list and put the first element at the end */
        first->next->next  = first;  
        /* tricky step -- see the diagram */
        first->next  = NULL;          
        /* fix the head pointer */
        *head_ref = rest;              

    This solution is from geeksforgeeks, here's the link http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

    The last statement about fixing head_ref pointer is confusing me. Let's take an example of 1->2->3

    n first recursion: first=1, rest=2
    in second recursion: first=2, rest=3
    in last recursion: first=3, rest=null

    and from that point we go back, and in each step we assign *headRef=rest
    finally we come back at first step our rest was 2 and we assign *headRef=2
    but we need rest point to 3 not 2.
    I am sure I am missing something here but I could not resolve this please help me out
    if possible with drawings!!!

    Thank you in advance

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.