# 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.

## 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 *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
}

// 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 on other sites

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 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