二重リンクリストの逆の部分

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は、forループの最初にNULLを指している必要があります。あなたはより効果的に考えることができます。 t->next->next =t->nextが必要です。

Answer 2

メソッドパラメータでは、「参照」と「ポインタ」を混合しています。

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

多分あなたはどういう意味ですか？

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

Answer 3

あなたは[最初に、最後の]のセグメントを逆にした場合、あなたのコードがするように、あなたは、last->nextに、ではないfirst->prevにfirst->nextセットをしたいです。

Answer 4

ノード1のprevポインタがNULLで、ノード1の次に割り当てるため、問題は最初のノードで発生します。ノード5の隣に1を割り当てる必要があります

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