warpstar - 8 months ago 32

Java Question

This method right below reverses a doubly linked list with n elements. I dont understand how this really works. I have added comments, please correct me if I am wrong. I am not sure how the traversing process works.

`public void reverseDLL( ) {`

Node temp=head; //swap head and tail

head=tail; // head now points to tail

tail=temp; //tail points to head

//traverse the list swapping prev and next fields of each node

Node p=head; //create a node and point to head

while(p!=null) //while p does not equal null

{ //swap prev and next of current node

temp=p.next; // p.next does that not equal null? confusing.

p.next=p.prev; //this line makes sense since you have to reverse the link

p.prev=temp; //having trouble visualizing this.

p=p.next;//advance current node which makes sense

}

}

Answer

Let's try stepping through the code a few lines at a time.

```
Node temp=head;
head=tail;
tail=temp;
```

Here we are just setting up some variables. We are swapping our head to point to the tail and the tail to the head.

Now we define our starting node. This is our new head that used to be the tail.

```
Node p=head; //create a node and point to head
while(p!=null)
{
temp=p.next;
```

At this point, this is what we are looking at (note: if this is the first iteration, `next`

would point to null but that doesn't matter, just assume A is null for that case):

So we have `next`

pointing to A and `prev`

pointing to B. We want these to be swapped. To do so, we go ahead and assign `next`

to `prev`

(which points to B) so now `next`

and `prev`

both point to B.

```
p.next=p.prev;
```

Great! We're half way there. Now we have:

Now our last step is to have `prev`

point to what `next`

used to point to. How are we going to get to it? Luckily, we stored what `next`

used to point to (in other words, A) in `temp`

. So let's use that to assign `prev`

.

```
p.prev=temp;
```

Alas, we have:

Now this node has been swapped, and we move on to the next.

```
p=p.next;
}
```

Rinse and repeat.

All together:

```
Node p=head; //create a node and point to head
while(p!=null)
{
temp=p.next;
p.next=p.prev;
p.prev=temp;
p=p.next;
}
```