Обръщане на свързан списък между два възела

Работя върху малко домашно за клас по 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