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

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

Daniel
Guest
Posts: n/a

 10-25-2004
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)
{ next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
}

CBFalconer
Guest
Posts: n/a

 10-25-2004
Daniel wrote:
>
> 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

--
Chuck F ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.

Nick Austin
Guest
Posts: n/a

 10-25-2004
On 24 Oct 2004 18:27:46 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (Daniel) wrote:

>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)
> { 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
Guest
Posts: n/a

 10-26-2004
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)
{
{
next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
next = q->next;
q->next = q->prev;
q->prev = next;
}

Cheers,
Sriram.

"Daniel" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> 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;
> { next = q->next;
> q->next = q->prev;
> q->prev = next;
> q = next;
> }
> }

Guest
Posts: n/a

 10-26-2004
In article <cll5u9\$2ie\$(E-Mail Removed)>,
"Sriram Rajagopalan" <(E-Mail Removed)> wrote:

> 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)
> {
> {
> next = q->next;
> q->next = q->prev;
> q->prev = next;
> q = next;
> }
> next = q->next;
> q->next = q->prev;
> q->prev = next;
> }

Try:

{

do {
NodePtr next;

next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}

Cheers,
- jonathan

pete
Guest
Posts: n/a

 10-27-2004
Daniel wrote:
>
> 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;
> { next = q->next;
> q->next = q->prev;
> q->prev = next;
> q = next;
> }
> }

{

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

--
pete