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

Discussion in 'C Programming' started by Daniel, Oct 25, 2004.

  1. Daniel

    Daniel Guest

    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;
    }
    }
     
    Daniel, Oct 25, 2004
    #1
    1. Advertising

  2. Daniel

    CBFalconer Guest

    Re: What's wrong in my function of reverse the doubly linked list withdummy node.

    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 () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Oct 25, 2004
    #2
    1. Advertising

  3. Daniel

    Nick Austin Guest

    On 24 Oct 2004 18:27:46 -0700, (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.
     
    Nick Austin, Oct 25, 2004
    #3
  4. 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" <> wrote in message
    news:...
    > 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;
    > }
    > }
     
    Sriram Rajagopalan, Oct 26, 2004
    #4
  5. In article <cll5u9$2ie$>,
    "Sriram Rajagopalan" <> 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
     
    Jonathan Adams, Oct 26, 2004
    #5
  6. Daniel

    pete Guest

    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
     
    pete, Oct 27, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    935
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    463
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    330
    Terry Reedy
    Sep 5, 2005
  4. dssuresh6

    need for doubly linked list

    dssuresh6, Nov 18, 2004, in forum: C Programming
    Replies:
    4
    Views:
    635
    J. J. Farrell
    Nov 19, 2004
  5. Replies:
    2
    Views:
    1,005
    Ivan Vecerina
    May 3, 2006
Loading...

Share This Page