Реверсирование связанного списка между двумя узлами

Я работаю над домашним заданием для класса CS и немного борюсь с функцией, предназначенной для обращения двусвязного списка между двумя заданными узлами. Я очень запутался в том, что я делаю неправильно, и я искал Google и SO, и я не могу найти ничего, что могло бы мне помочь.

У меня есть двусвязный список, и я, по сути, использую эту функцию как вспомогательную функцию, чтобы перевернуть ее между двумя узлами, которые заданы как параметры функции.

Ниже приведен код шаблона, прокомментированный, чтобы вы знали ход моих мыслей.

template <class T>
void List<T>::reverse( ListNode * & startPoint, ListNode * & endPoint )
{
    //make sure that none of the pointers are null and that the start and 
    //end points aren't the same
    if(startPoint == NULL || endPoint == NULL || startPoint == endPoint)
        return;
    //Make two nodes denoting everything happening before the
    //start and everything after the end
    ListNode *before = NULL;
    ListNode *after = NULL;
    if(startPoint->prev != NULL)
        before = startPoint->prev;
    if(endPoint->next != NULL)
        after = endPoint->next;
    ListNode *temp = startPoint;
    ListNode *temp2;
    //run a loop actually reversing the list. I have identified
    //that this is where the problem is happening (obviously)
    //for some reason the prev pointer for every node is being set to null
    //so if I had a linked list with 1 2 3 4 5
    //after running this it's just 5
    while(temp!=endPoint && temp!=NULL){
        temp2 = temp->next;
        if(temp->prev!=NULL);
            temp->next = temp->prev;
        if(temp2!=NULL)
            temp->prev = temp2;
        temp = temp2;

    }
    //switch around the end and start pointers
    endPoint = startPoint;
    startPoint = temp;
    //make sure it's integrated into the rest of the linked list
    if(before != NULL){
        before->next = startPoint;
        startPoint->prev = before;
    }
    if(after != NULL){
        after->prev = endPoint;
        endPoint->next = after;
    }
}

Итак, есть идеи? Я понял, где происходит проблема и в чем она заключается, но я не понял, почему это происходит и как это исправить.

Кроме того, не стесняйтесь, дайте мне знать, если вы думаете, что я делаю что-то лишнее или ненужное, у меня есть склонность иногда делать это.

РЕДАКТИРОВАТЬ: это инклюзивная функция, поэтому, если вы вызвали ее в связанном списке {1, 2, 3, 4, 5, 6} с указателями, указывающими на узлы со значением 2 и 5, тогда связанный список будет изменен на { 1, 5, 4, 3, 2, 6}


c++ data-structures linked-list doubly-linked-list
person Tejas Sharma    schedule 20.02.2015    source источник
comment
Если ваш начальный список {1, 2, 3, 4, 5, 6}, а ваши указатели аргументов указывают на 2 и 5, должен ли результат быть {1, 2, 4, 3, 5, 6} или {1, 5, 4, 3, 2, 6}?   -  person Beta    schedule 21.02.2015
comment
Если указатели аргументов равны 2 и 5, то это должно быть {1, 5, 4, 3, 2, 6}. Я добавлю к вопросу, что он включительно   -  person Tejas Sharma    schedule 21.02.2015
comment
Я думаю, что вижу проблему, и я работаю над ответом. Для дальнейшего использования минимальный полный пример сделает это намного проще.   -  person Beta    schedule 21.02.2015

Ответы (1)


arrow_upward
1
arrow_downward

Проблема с концами подсписка.

Вы не привели полный пример (что могло бы помочь), но предположим, что мы начинаем со списка {1, 2, 3, 4, 5} и пытаемся reverse(s, e), где s и e — указатели, указывающие на 2 и 4. (Итак, наш желаемый результат — {1, 4, 3, 2, 5}.)

Здесь мои навыки рисования ASCII терпят неудачу, но указатели «следующий» и «предыдущий» выглядят так:

1-->2-->3-->4-->5

1<--2<--3<--4<--5

Когда управление покидает цикл while, они выглядят так:

1<->2<--3   4-->5
1   2-->3<->4<--5

это почти то, что мы планировали, но процесс остановился на одном узле слишком рано (4 не были реверсированы). После его «интеграции в остальной список» они выглядят так:

  ________ ___
 /   /    \   \
1   2<--3  >4-->5
1   2-->3-->4   5
 \___\_____/___/

Не очень ясно, но если вы начнете с начала списка и будете двигаться вперед, он будет {1, 4, 5}, а если вы двигаетесь назад с конца, он будет {5, 2, 3, 4, 1}. Вы нарушили условие двойной связи: если a.next указывает на b, то b.prev указывает на a, и наоборот.

Мой совет (кроме того, чтобы рисовать больше стрелок карандашом и бумагой) состоит в том, чтобы удалить подсписок из списка, перевернуть его, а затем снова соединить; попытка изменить его на месте сбивает с толку.

person Beta    schedule 21.02.2015