• + 26 comments

    Take an example, 1 -> 2 -> 3 -> null
    First Call to the function,

    1 -> 2 -> 3 -> null
    ^
     |
    head

    head is not null OR head.next is not null,
    Jump to ELSE block,
    Assigning Node remaining = Reverse(head.next);
    //Statements after this to be executed later



    Second Call to the function,

    1 -> 2 -> 3 -> null
                ^
                 |
              head

    head is not null OR head.next is not null,
    Jump to ELSE block,
    Assigning Node remaining = Reverse(head.next);
    //Statements after this to be executed later



    Third Call to the function,

    1 -> 2 -> 3 -> null
                            ^
                             |
                        head

    head is not null OR BUT head.next is null,
    return head; //Now important thing is to remember what we are returning, (head, pointing to 3)



    Attaboy! Time Machine time!

    1 -> 2 -> 3 -> null
                            ^
                             |
                        head

    Resuming Second Call to the function,
    Second call,
    head here is equal to the reference to the node which has data = 2

    1 -> 2 -> 3 -> null
                ^
                 |
              head


    Node remaining is equal to a reference to the node, which has 3 inside it.

    head.next.next = head;
    //head is reference to node having data as 2
    head.next = null;

    So the status is now,
    1 -> 2 <- 3 -> null
                ^          ^
                 |           |
              head    remaining

    We reach the last line of second function,

    return remaining;




    Resuming First Call to the function,
    Second call to the function returned 'remaining' which is a reference to the node which has 3 as its data,
    Whereas we know that, head in the first function instance is equal to the reference to the node which has data = 1

    1 -> 2 -> 3 -> null
    ^
    |
    head


    Node remaining is STILL equal to a reference to the node, which has 3 inside it.

    head.next.next = head;
    //head is reference to node having data as 1
    head.next = null;

    So the status is now,
    null <-1 <- 2 <- 3 -> null
                    ^                     ^
                     |                      |
                    head    remaining

    We reach the last line of first copy of function

    return remaining;

    And the head of the reversed linked list is returned.