обратная часть двусвязного списка

Question

Я пытаюсь реализовать свой собственный класс списков, но у меня возникают проблемы при обращении только части моего списка.

Соответствующий код:

void List<T>::reverse(ListNode * & head, ListNode * & tail)
{

    ListNode* t;
    ListNode* curr = head;
    ListNode * funtail = tail;
    int stop=0;
    while(stop==0)
    {
        if(curr==funtail)
        {
            stop = 1;
        }
        t = curr->prev;
        curr->prev = curr->next;
        curr->next = t;
        curr = curr->prev;
    }
    t = tail;
    tail = head;
    head = t;
}

Если я начну со списка

1 2 3 4 5 6 7 8 9 10

и я передаю указатели на 1 и 4, тогда список должен выглядеть следующим образом:

4 3 2 1 5 6 7 8 9 10

Проблема в том, что мой список возвращается как

1

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

Answer 1

Если вы перевернете сегмент [первый, последний], вы хотите, чтобы first->next был установлен на last->next, а не на first->prev, как ваш код.

Answer 2

Более простое решение.

/**
 * Traverses half of the list and swaps a node with another node(
  here by termed as the reflection node)
 * which lies at a position = listSize - (i +1) for every i.
 * Reassignment of element is not needed, hence a soul saver from
 * the copy constructor thing ( '=' assignment operator stuff).
 */
template <typename E> void DLinkedList<E>::reverse(){
    int median = 0;
    int listSize = size();
    int counter = 0;

    if(listSize == 1)
        return;

/**
 * A temporary node for swapping a node and its reflection node
 */
DNode<E>* tempNode = new DNode<E>();

for(int i = 0; i < listSize/2 ; i++){
    DNode<E>* curNode = nodeAtPos(i);
  // A node at 'i'th position
    DNode<E>* reflectionNode = nodeAtPos(listSize - (i + 1));   
 // Reflection of a node considering the same distance from the median

        /**
         * swap the connections from previous and next nodes for current and 
             * reflection nodes
         */
        curNode->prev->next = curNode->next->prev = reflectionNode;

        reflectionNode->prev->next = reflectionNode->next->prev = curNode;

        /**
         * swapping of the nodes
         */
        tempNode->prev = curNode->prev;
        tempNode->next = curNode->next;

        curNode->next = reflectionNode->next;
        curNode->prev = reflectionNode->prev;

        reflectionNode->prev = tempNode->prev;
        reflectionNode->next = tempNode->next;
    }

    delete tempNode;
}

template <typename E> int DLinkedList<E>::size(){
    int count = 0;
    DNode<E>* iterator = head;

    while(iterator->next != tail){
        count++;
        iterator = iterator->next;
    }
    return count;
}

template <typename E> DNode<E>* DLinkedList<E>::nodeAtPos(int pos){
    DNode<E>* iterator = head->next;
    int listSize = size();
    int counter = 0;
    while(counter < pos){
        iterator = iterator->next;
        counter++;
    }

    return iterator;
}

Answer 3

Ваш head->prev должен указывать на NULL в первом цикле for. Вы лучше подумайте и внедрите диграматически это будет полезно. Вам нужно t->next->next =t->next.

Answer 4

Проблема возникает для первого узла, так как указатель prev узла 1 равен NULL, и вы назначаете его следующему узлу 1Вы должны назначить 1 рядом с Узлом 5

Answer 5

В параметрах вашего метода вы смешиваете «Указатели» с «Ссылками».

void List::reverse(ListNode * & head, ListNode * & tail)

Может быть, вы имеете в виду?

void List::reverse(ListNode* head, ListNode* tail)