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

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;

}

Answers


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.


I made a diagram in dot that I think will graphically explain what's going on:

Link to full-sized image

And here's the (sloppy) dot source in case anyone cares:

digraph g {
    label = "Start"
    subgraph cluster_1
    {
        a1 -> b1 -> c1;
        current1 -> a1;
        result1
        a1 [label="a"]
        b1 [label="b"]
        c1 [label="c"]
        current1 [label="current"]
        result1 [label="result"]
    }
    label = "Once through loop"
    subgraph cluster_2
    {
        current2 -> b2;
        result2 -> a2;
        b2 -> c2;
        a2 [label="a"]
        b2 [label="b"]
        c2 [label="c"]
        current2 [label="current"]
        result2 [label="result"]
    }
    label = "Twice through loop"
    subgraph cluster_3
    {
        current3 -> c3;
        result3 -> b3;
        b3 -> a3;
        a3 [label="a"]
        b3 [label="b"]
        c3 [label="c"]
        current3 [label="current"]
        result3 [label="result"]
    }
    label = "Final"
    subgraph cluster_4
    {
        result4 -> c4 -> b4 -> a4;
        a4 [label="a"]
        b4 [label="b"]
        c4 [label="c"]
        current4 [label="current"]
        result4 [label="result"]
    }
    label = ""

}

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


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)

See here for a good explanation. Here is the excerpt:

public class List {
    private class Node {
        int data;
        Node next;
    }
   private Node head;

   public void reverse() {
      if (head == null) return;
      Node prev = null,curr = head,next = null;
      while (curr != null) {
         next = curr.next;
         curr.next = prev;
         prev = curr;
         curr = next;
      }
      head = prev;
   }
}

The list:
==========
1->2->3->4->5
------------------------------------------------------------------
Running of the code:
============================
At start:
**********
head = 1;
prev = null,curr = 1, next = null
1st iteration of while loop:
******************************
next = 2;
2->3->4->5
curr.next = null;
1->null
prev = 1;
1->null
curr = 2;
2->3->4->5
2nd iteration of while loop:
******************************
next = 3
3->4->5
curr.next = 1
2->1->null
prev = 2
2->1->null
curr = 3
3->4->5
3rd iteration of while loop:
******************************
next = 4
4->5
curr.next = 2
3->2->1->null
prev = 3
3->2->1->null
curr = 4
4->5
4th iteration of while loop:
******************************
next = 5
5->null
curr.next = 3
4->3->2->1->null
prev = 4
4->3->2->1->null
curr = 5
5->null
5th iteration of while loop:
******************************
next = null
null
curr.next = 4
5->4->3->2->1->null
prev = 5
5->4->3->2->1->null
curr = null
There is no 6th iteration and the while loop terminates since 
curr is null and the check is for curr != null.
last statement: 
==================
head = prev
This statement leaves the list reversed with referencing head with the reversed node prev 
to become the new head node.

Need Your Help

Showing notification independently of the current view PhoneJS?

jquery ios web-applications knockout.js phonejs

I'm using PhoneJS to make a mobile web app. It requires a login, and I'd like to show a 'toast' message with the result (error, success, etc)