• Advertisement
Sign in to follow this  

Problems with reversing a sublist of a linked list

This topic is 1242 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I'm trying to implement a doubly linked list again after horribly failing the last time I tried a few years ago, and I was remined again why I disliked reversing the list through pointer exchange.
// assume ListNode is a valid type
// and head/tail are initialized properly somewhere and filled with data
ListNode *head;
ListNode *tail;

void reverse(ListNode&* start, ListNode&* end){
    ListNode *c = start;
    while(c && c != end->next){
        std::swap(c->next, c->prev);
        c = c->prev;
    }
    // some extra logic goes here, i'm not sure what
}

// reverse(head, tail), reverse(head->next->next, tail->prev) should all be
// valid function calls on the dll
I can never seem to figure out what that extra bit of logic is to correctly update the references and pointers from other nodes.
std::swap(startPoint->next, endPoint->prev);
std::swap(startPoint, endPoint);
does not seem to be enough to correct the pointers.

Share this post


Link to post
Share on other sites
Advertisement

EDIT:  Sorry, I thought you were just going from head to end, not some positions in-between.  Nevermind the below, don't have time to think of a full solution :)  GL.

 

It looks OK to me, assuming you add the std::swap(start, end)l after the loop.  You also don't need the extra while conditional.  I'd do this FWIW.

void reverse(ListNode&* start, Listnode&* end)
{
  ListNode* c = start;
 
  while(c != NULL) {
    ListNode* next = c->next;
    c->next = c->prev;  // you could use std::swap here I suppose, but I'm not as familiar with it as just doing it myself.
    c->prev = next;
    c = next;
  }
  ListNode* tempStart = start;
  start = end;
  end = tempStart;
}

I would assume using std::swap would work as well like you have, but I'm not familiar with it so I just do it myself, and I would also assume std::swap (start, end) would be the right call too.  You can always add some temps just to check it does what you think.

Edited by BeerNutts

Share this post


Link to post
Share on other sites
Thous kinds of problems are best solved with a pencil and paper - don't annoy your brain with bizarre gymnastics it is not built for.

This is supposed to turn a list of: X-start-B-C-end-Y into X-end-C-B-start-Y.
void reverse(ListNode* start, ListNode* end) {
    assert(at && end);
    ListNode *at = start, _start = start->prev, _end = end->next;
    while(at != end) {
        std::swap(at->next, at->prev);
        at = at->prev;
    }
    std::swap(end->next, end->prev);
    end->prev = _start;
    start->next = _end;
    if(_start) _start->next = end;
    if(_end) _end->prev = start;
}
... my guess. Have fun covering it with tests.

edit:
"ListNode&*" ... wut? Did you mean "ListNode*&"?

edit2:
(what compiler can make sense out of "ListNode&*"? ... and could someone explain that to me :/ ) Anyway, question: what is supposed to happen here "reverse(foo->prev, bar->prev)"? The path you seem to try leads to a dark place.

Wrap your list implementation in a class, so "reverse" can update the list start and end points when needed (else clauses for the example code). Edited by tanzanite7

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement