What's wrong in my function of reverse the doubly linked list with dummy node.

[Daniel]

I need to reverse the doubly linked list with dummy node. I think the
solution is to exchange each node pointers' next and previous address.
But what's wrong in my function?
Thanks

void reverse_list(NodePtr p)
{ NodePtr next, q=p, head=p->prev;
while (q != head)
{ next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
}

 

[CBFalconer]

I need to reverse the doubly linked list with dummy node. I think
the solution is to exchange each node pointers' next and previous
address. But what's wrong in my function?

If it is doubly linked there is no need to reverse it. Just follow
the other links.

 

[Nick Austin]

I need to reverse the doubly linked list with dummy node. I think the
solution is to exchange each node pointers' next and previous address.
But what's wrong in my function?
Thanks

void reverse_list(NodePtr p)
{ NodePtr next, q=p, head=p->prev;
while (q != head)
{ next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
}

You swap one node too few. Change the while loop to a do-while
loop so that the end condition is at the end of the loop.

Nick.

 

[Sriram Rajagopalan]

Dan,

As Nick said the unltimate node is not getting swapped.
But, do-while would also repeat the same mistake.

So, handle the ultimate case seperately as below:

I guess this shud work,

void reverse_list(NodePtr p)
{
NodePtr next, q=p, head=p->prev;
while (q != head)
{
next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
next = q->next;
q->next = q->prev;
q->prev = next;
}

Cheers,
Sriram.

 

[Jonathan Adams]

Dan,

As Nick said the unltimate node is not getting swapped.
But, do-while would also repeat the same mistake.

Not if you write it correctly.

So, handle the ultimate case seperately as below:

I guess this shud work,

void reverse_list(NodePtr p)
{
NodePtr next, q=p, head=p->prev;
while (q != head)
{
next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
next = q->next;
q->next = q->prev;
q->prev = next;
}

Try:

void reverse_list(NodePtr head)
{
NodePtr q = head;

do {
NodePtr next;

next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
} while (q != head);
}

Cheers,
- jonathan

 

[pete]

I need to reverse the doubly linked list with dummy node. I think the
solution is to exchange each node pointers' next and previous address.
But what's wrong in my function?
Thanks

void reverse_list(NodePtr p)
{ NodePtr next, q=p, head=p->prev;
while (q != head)
{ next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
}

NodePtr reverse_list(NodePtr head)
{
NodePtr q = head;

while(q != NULL) {
head = q;
q = q -> next;
head -> next = head -> prev;
head -> prev = q;
}
return head;
}