C++中的反向雙鏈表

Question

我一直在想如何顛倒雙向鏈表的順序，但由於某種原因，在我的函數void reverse()運行while循環一次，然後由於某種原因崩潰。爲了回答一些問題，我在兄弟們的幫助下自我教導自己。這還不是全部的代碼，但我有一個display()功能，按時間順序打印所有節點從start_ptr和激活像

case 1 : add_end(); break; 
    case 2 : add_begin(); break; 
    case 3 : add_index(); break; 
    case 4 : del_end(); break; 
    case 5 : del_begin(); break; 
    case 6 : reverse(); break; 

某些功能的開關這是我的代碼的感性：

#include <iostream> 
using namespace std; 

struct node 
{ 
    char name[20]; 
    char profession[20]; 
    int age; 
    node *nxt; 
    node *prv; 
}; 

node *start_ptr = NULL; 

void pswap (node *pa, node *pb) 
{ 
    node temp = *pa; 
    *pa = *pb; 
    *pb = temp; 
    return; 
} 

void reverse() 
{ 
    if(start_ptr==NULL) 
    { 
     cout << "Can't do anything" << endl; 
    } 
    else if(start_ptr->nxt==NULL) 
    { 
     return; 
    } 
    else 
    { 
     node *current = start_ptr; 
     node *nextone = start_ptr; 
     nextone=nextone->nxt->nxt; 
     current=current->nxt; 
     start_ptr->prv=start_ptr->nxt; 
     start_ptr->nxt=NULL; 
     //nextone=nextone->nxt; 
     while(nextone->nxt!= NULL) 
     { 
      pswap(current->nxt, current->prv); 
      current=nextone; 
      nextone=nextone->nxt; 
     } 
     start_ptr=nextone; 
    } 
} 

Answer 1

試試這個：

node *ptr = start_ptr; 
while (ptr != NULL) { 
    node *tmp = ptr->nxt; 
    ptr->nxt = ptr->prv; 
    ptr->prv = tmp; 
    if (tmp == NULL) { 
     end_ptr = start_ptr; 
     start_ptr = ptr; 
    } 
    ptr = tmp; 
} 

Answer 2

您可以簡化reverse()不少。我會做這樣的事情：

void reverse() 
{ 
    if(start_ptr == NULL) 
    { 
     cout << "Can't do anything" << endl; 
    } 
    else 
    { 
     node *curr = start_ptr; 
     while(curr != NULL) 
     { 
      Node *next = curr->next; 
      curr->next = curr->prev; 
      curr->prev = next; 
      curr = next; 
     } 
     start_ptr = prev;  
    } 
} 

說明：基本的想法很簡單，就是訪問每個Node和交換鏈接previous和next。當我們將curr移動到下一個Node時，我們需要存儲下一個節點，所以當我們將curr.next設置爲prev時，我們仍然有一個指向它的指針。

Answer 3

編輯：我的第一個實現，這是正確的，但不完美。 你的實現非常複雜。你可以試試這個：

node * reverse(Node * start_ptr) 
{ 
    Node *curr = start_ptr; 
    Node * prev = null; 
    Node * next = null; 
    while(curr) 
    { 
     next = curr->nxt; 
     curr->nxt = prev; 
    curr->prv = next; 
     prev = curr; 
     curr = next; 
    } 
    return start_ptr=prev; 
} 

這是我更新的解決方案：

node * reverse() 
{ 
    node *curr = start_ptr; 
    node * prev = NULL; 
    node * next = NULL; 
    while(curr) 
    { 
     next = curr->nxt; 
     curr->nxt = prev; 
     curr->prv = next; 
     prev = curr; 
     curr = next; 
    } 
    return start_ptr=prev; 
} 

的邏輯是正確的。但問題是我接受了輸入參數start_ptr。這意味着我正在返回它的本地副本。現在它應該工作。

Answer 4

你的pswap函數是錯誤的 你應該交換指針而不是嘗試創建臨時對象並交換它們。 應該是這樣的（可能有其他錯誤後）

void pswap (node *&pa, node *&pb) 
{ 
    node* temp = pa; 
    pa = pb; 
    pb = temp; 
    return; 
} 

Answer 5

我建議保持一個鏈接到最後一個節點。
如果沒有，找到最後一個節點。 使用「以前的」鏈接遍歷列表（或者在你的情況下，prv）。

沒有必要實際改變周圍的鏈接。使用prv指針遍歷將自動以相反的順序訪問節點。

Answer 6

看

valuesnextone=nextone->nxt->nxt; 

這裏nextone->nxt可以爲空。

除此之外，嘗試使用交換功能指針指針。

Answer 7

簡單的解決方案。逆轉小於一半以上的列表

template<typename E> void DLinkedList<E>::reverse() { 
    int median = 0; 
    int listSize = size(); 
    int counter = 0; 

    if (listSize == 1) 
    return; 

    DNode<E>* tempNode = new DNode<E>(); 

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

    DNode<E>* headCursor = head; 
    DNode<E>* tailCursor = tail; 

    for (int i = 0; i < listSize/2; i++) { 
     cout << i << "\t"; 

     headCursor = headCursor->next; 
     tailCursor = tailCursor->prev; 

     DNode<E>* curNode = headCursor; 
     DNode<E>* reflectionNode = tailCursor; 

     if (listSize % 2 == 0 && listSize/2 - 1 == i) { 
      /** 
      * insert a dummy node for reflection 
     * for even sized lists 
     */ 
     curNode->next = dummyNode; 
     dummyNode->prev = curNode; 

     reflectionNode->prev = dummyNode; 
     dummyNode->next = reflectionNode; 

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

    if (listSize % 2 == 0 && listSize/2 - 1 == i) { 
     /** 
     * remove a dummy node for reflection 
     * for even sized lists 
     */ 
     reflectionNode->next = curNode; 
     curNode->prev = reflectionNode; 
    } 

    /** 
    * Reassign the cursors to position over the recently swapped nodes 
    */ 
     tailCursor = curNode; 
     headCursor = reflectionNode; 

    } 

    delete tempNode, dummyNode; 
} 

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

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

Answer 8

A中的數的總迭代的非常簡單的，並使用兩個指針O（n）的溶液：

開始=的雙重LL

struct node *temp, *s; 
s = start; 

while(s != NULL){ 
    temp = s->prev; 
    s->prev = s->next; 
    s->next = temp; 
    s = s->prev; 
} 

//if list has more than one node 
if(current != NULL){ 
    start = temp->prev; 
} 

Answer 9

頭

我的代碼用於反轉雙向鏈表，

Node* Reverse(Node* head) 
{ 
// Complete this function 
// Do not write the main method. 


if(head != NULL) { 

    Node* curr = head; 
    Node* lastsetNode = curr; 
    while(curr != NULL) { 

     Node* frwdNode = curr->next; 
     Node* prevNode = curr->prev; 


     if(curr==head) {     
      curr->next = NULL; 
      curr->prev = frwdNode; 
      lastsetNode = curr; 
     } 
     else { 
      curr->next = lastsetNode; 
      curr->prev = frwdNode; 
      lastsetNode = curr; 
     } 



     curr = frwdNode; 
    } 

    head = lastsetNode; 
} 


return head; 
}