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

Question

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

Revelant код:

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

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

Answer 2

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

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

Возможно, вы имеете в виду?

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

Answer 3

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

Answer 4

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

Answer 5

Простое решение.

/** 
* 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; 
}