Visual Explanation Guidance needed for reversal of Linked List datastructure code ?

Question

Hi,

I have following piece of code for reversing the linked list. I am getting confused in while loop and so would certainly appreciate if someone can provide visual explanation of how actually it's working.

 static void Reverse (struct node** headRef)
{
     struct node* result = NULL;
     struct node* current = *headref;
     struct node* next;

     while(current != NULL)
     {
        next = current->next;
        current->next = result;
        result = current;

        current = next;
     }     
     *headRef = result;

}

Answer 1

list looked like:

=>(1) => => => => => => => => =>(10)

we reversed every piece of the list

<=(1) => => => => => => => => =>(10)
<=(1) <= => => => => => => => =>(10)
<=(1) <= <= => => => => => => =>(10)
...
<=(1) <= <= <= <= <= <= <= <= <=(10)

so, now start is in the end, and we can look at the list from the different point and see:

=>(10) => => => => => => => => =>(1)

Answer 2

Check out this site for a visual representation.
There looks like a good codeproject explanation here too (See technique 3).

Answer 3

OK, here's my attempt to make valya's answer even clearer (though I thought it was pretty good already):

Say we have this list:

// a->b->c->d->e->NULL

We start at the first node, a, which contains a pointer (next) to b:

// a->b ...

The line next = current->next; sets next to b (simple enough). The next line current->next = result; does this:

// NULL<-a  b ... (notice there is no longer a pointer from a to b)

Then we have result = current; which sets result to a (again, simple enough). And finally, we have the all important current = next;, which set current to b.

So on the next iteration of the while loop, with next set to b, result set to a, and current set to b, we start over:

next = current->next;

// NULL<-a<-b  c ...
current->next = result;

result = current;

Then we do it again:

next = current->next;

// NULL<-a<-b<-c  d ...
current->next = result;

result = current;

Once we've gotten to the last item in the linked list (e in this example), this happens:

next = current->next; // next becomes NULL

// NULL<-a<-b<-c<-d<-e
current->next = result;

result = current; // result is now e

current = next; // current is now NULL

Now, since current is NULL, the while loop terminates, and we are left with:

*headRef = result;

which, as you can see now, makes headRef point to e, treating e as the new first item in our linked list, with e->next pointing to d, d->next pointing to c, etc.

Answer 4

You can find the visual representation here.. http://www.cpp-programming.net/c-tidbits/reverse-linked-list-using-3-ptrs/