Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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)
{ NodePtr next, q=p, head=p->prev;
while (q != head)
{ next = q->next;
q->next = q->prev;
q->prev = next;
q = next;
}
}
 
Reply With Quote
 
 
 
 
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
the other links.

--
Chuck F ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


 
Reply With Quote
 
 
 
 
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)
>{ 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.

 
Reply With Quote
 
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)
{
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.

"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;
> while (q != head)
> { next = q->next;
> q->next = q->prev;
> q->prev = next;
> q = next;
> }
> }



 
Reply With Quote
 
Jonathan Adams
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)
> {
> 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
 
Reply With Quote
 
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;
> 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;
}

--
pete
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
doubly linked list murali@pune Java 3 03-24-2006 09:30 AM
Doubly linked list Joe Estock C Programming 6 03-19-2006 11:23 PM
Warning when doubly linked list is defined gloablly chand Python 7 09-05-2005 07:28 PM
need for doubly linked list dssuresh6 C Programming 4 11-19-2004 03:22 AM
Does any one have heap sorting with doubly linked list in C? darth C Programming 0 04-30-2004 11:51 AM



Advertisments