Skip to main content
GameDev.net gamedev.net
🔒 Locked

Problems with reversing a sublist of a linked list

Started by incertia Sep 29, 2014 at 7:25 PM 2 replies 3.4k views
Original Post
incertia
incertia
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.
what
BeerNutts
BeerNutts

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.

My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)
tanzanite7
tanzanite7
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).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.