顛倒鏈表？

我試圖扭轉下列鏈表的順序，我這樣做了，但反轉列表似乎沒有打印出來。我哪裏錯了？顛倒鏈表？

//reverse the linked list 
    #include <iostream> 
    using namespace std; 

    struct node{ 
     int number; 
     node *next; 
    }; 

    node *A; 

    void addNode(node *&listpointer, int num){ 
     node *temp; 
     temp = new node; 
     temp->number = num; 
     temp->next = listpointer; 
     listpointer = temp; 
    } 

    void reverseNode(node *&listpointer){ 
     node *temp,*current; 
     current = listpointer; 
     temp = new node; 
     while (true){ 
      if (current == NULL){ 
       temp = NULL; 
       break; 
      } 
      temp->number = current->number; 
      current = current->next; 
      temp = temp->next; 
     } 
     listpointer = temp; 
    } 

    int main(){ 
     A = NULL; 
     addNode(A,1); 
     addNode(A,2); 
     addNode(A,3); 

     while (true){ 
      if (A == NULL){break;} 
      cout<< A->number << endl; 
      A = A->next; 
     } 
     cout<< "****" << endl; 
     reverseNode(A); 

     while (true){ 
      if (A == NULL){break;} 
      cout<< A->number << endl; 
      A = A->next; 
     } 

     cout<< "****"<< endl; 

     return 0; 
    }

來源

2010-05-22 silent

我想這是家庭作業。那麼，你允許使用雙向鏈表和/或遞歸嗎？ – 2010-05-22 09:51:46

不是家庭作業，但我需要知道如何做到這一點沿途 – silent 2010-05-22 09:58:12

嗯，我注意到的第一件事情是，你正在做

臨時=新節點

，然後，在每一次互動：

TEMP = TEMP->未來

但你永遠不會分配temp-> next

所以當你最終重載列表指針時，你肯定會給出一些有趣的價值。

來源

2010-05-22 09:49:20 garph0

你也在泄漏記憶。一般而言，您的反轉算法不起作用。反轉單個鏈表的最好方法是遞歸執行：這裏還有一個相關的問題：http://stackoverflow.com/questions/2434411/linked-list-recursive-reverse – garph0 2010-05-22 09:59:56

還有一個簡單的迭代算法。參見[反向單鏈表]（http://stackoverflow.com/questions/1432205/reverse-a-single-chained-list）。 – 2010-05-22 10:29:16

沒有檢查你的代碼我問你這個問題，你確定你的鏈表正在工作嗎？

來源

2010-05-22 09:49:09 Marthin

yup鏈表工作正常，只需要反饋在reverseNode函數 – silent 2010-05-22 09:51:05

鏈接列表似乎插入項目的開始。我不確定這是否是故意的。 – 2010-05-22 09:53:30

你這樣做：

while (true){ 
    if (current == NULL){ 
     temp = NULL; 
     break; 
    } 
    temp->number = current->number; 
    current = current->next; 
    temp = temp->next; 
}

假設它可以作爲您的預期。當存在時，temp將是NULL，對吧？

listpointer = temp; <=> listpointer = NULL;

所以這可能是一個問題。

來源

2010-05-22 09:51:21 nc3b

-1

爲什麼不：

措施列表的長度
填補，直到你達到你的現有列表大小的兩倍
轉到追加用零列表
逐個閱讀內容，直到您到達原始列表的末尾
而移動所述原始列表上：
拷貝當前節點的內容轉換成具有指針由

推進節點（（原始列表長度 - 當前節點指數）* 2 + 1）*節點的大小
在完成後，得到的第一個節點的指針原來的名單後，在逆轉列表

點

無需創建一個新的列表或在多個迭代工作或修改現有的數據結構（它不轉換爲雙鏈表）

來源

2010-05-22 10:06:51

1,2和4都需要與列表大小成比例的時間。 2使內存與其成正比。＃6似乎也需要向後移動或重複迭代到所需的索引（二次方）。我不認爲這個算法是合理的。 – 2010-05-22 10:19:14

它應該是這樣的 node +（（max-idx）* 2 + 1）* sizeof（node）= node-> number; node ++; – 2010-05-22 10:23:26

你不能做指針算術。這是一個鏈表。此外，指針運算爲你處理* sizeof *。 – 2010-05-22 10:27:52

void reverse(Node** list) { 
    Node* previous=NULL; 
    Node* current=*list; 
    while (NULL!=current) { 
     std::swap(previous, current->next); 
     std::swap(previous, current); 
    } 
    *list=previous; 
}

來源

2013-03-13 08:41:16

回答

相關問題