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

Question

Я работаю над некоторой домашней работой для класса 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; 
    } 
} 

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

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

EDIT: Это включенная функция, поэтому, если вы вызвали ее в связанном списке {1, 2, 3, 4, 5, 6} с указателями, указывающими на узлы со значениями 2 и 5, то связанный список изменить на {1, 5, 4, 3, 2, 6}

Answer 1

Проблема заключается в концах подсписок.

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

Это то, где мои навыки в искусстве ASCII терпят неудачу, но указатели «next» и «prev» как это:

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 и наоборот.

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