當傳遞給一個函數時，奇異鏈表會變成循環鏈表

我想通過使用C++來顛倒鏈表，然後打印出反轉的鏈表。當傳遞給一個函數時，奇異鏈表會變成循環鏈表

例如：原始列表是1-> 2-> 3 反轉後：3-> 2-> 1

但是，當我試圖打印出顛倒鏈表，3-> 2 - > 1成爲循環鏈表像3 < - > 2

以下是我的代碼：

#include <iostream> 
#include <sstream> 
using namespace std; 
class List{ 
public: 
    int value; 
    List *next; 
    List(int); 
    List(int, List *); 
}; 

List::List(int v){ 
    value = v; 
    next = NULL; 
} 

List::List(int v, List *ne){ 
    value = v; 
    next = ne; 
} 

string IntToString(int val){ 
    stringstream temp; 
    temp<<val; 
    return temp.str(); 
} 

void print(List *l){ 
    string output= ""; 
    while(l->next != NULL){ 
     output+=(IntToString(l->value)+"-->"); 
     l = l->next; 
    } 
    output+=(IntToString(l->value)+"-->NULL"); 
    cout<<output<<endl; 
} 

List reverse(List L){ 
    if(L.next == NULL) return L; 
    List remain = reverse(*(L.next)); 
    List *current = &remain; 
    while(current->next != NULL) 
     current = (current->next); 
    L.next = NULL; 
    current->next = &L; 
    //print(remain); 
    return remain; 
} 

List copy(List l){ 
    return l; 
} 

int main() { 
    List L3(3); 
    List L2(2, &L3); 
    List L1(1, &L2); 
    List L4 = reverse(L1); 
    print(&L4); 
    return 0; 
}

誰能告訴我，爲什麼出現這種情況？非常感謝！

來源

2012-09-03 LuZ

首先，我想指出一個list包含指向another list的指針是在概念上是錯誤的。

單獨創建列表節點類，例如，

struct ListNode { 
    int value; 
    Node *next; 
};

那麼你的List變，

class List { 
    ... 
    ListNode *head; 
    ... 
};

現在到倒車。在方法List reverse(List L),L只是一個局部變量。 它超出後範圍，

return remain; 
} // Here the scope of L ends

所以這在邏輯上是不正確的返回List其next價值爲L的位置，

current->next = &L; 
return remain; // remain is equal to *current and current->next = &L

這導致不確定的行爲您實現。

編輯：我有一些空閒時間，所以我想出了this implementation。它使用相同的算法，雖然修改了它被調用的的原始列表。

來源

2012-09-03 06:05:24 Hindol

太棒了！非常感謝！ – LuZ

我認爲你的逆向算法是正確的，但remain是一個局部變量，它在返回後無效，因此L4將包含無效指針。更改reverse()的簽名以獲取並返回List *。

 
List *reverse(List *L){ 
    if(L->next == NULL) return L; 
    List *remain = reverse(L->next); 
    List *current = remain; 
    while(current->next != NULL) 
     current = (current->next); 
    L->next = NULL; 
    current->next = L; 
    //print(remain); 
    return remain; 
}

來源

2012-09-03 02:27:25

問題用你的答案解決！謝謝！ – LuZ

只是看着你reverse()功能要創建名爲remain堆棧上的對象，並插入到你的列表中選擇此。這是行不通的：一旦你從函數返回（main()中的原始對象有同樣的問題，但在你離開main()後不嘗試使用它們），這個對象將會超出範圍。此外，你的reverse()函數似乎有二次性能，而它應該是線性的。我認爲像這樣的事情會做的伎倆：

List* reverse(List* head) { 
    List* tail(0); 
    while (head) { 
     List* tmp(head); 
     head = head->next; 
     tmp->next = tail; 
     tail = tmp; 
    } 
    return tail; 
}

上述實現還避免了遞歸。

來源

2012-09-03 05:29:01

當傳遞給一個函數時，奇異鏈表會變成循環鏈表

回答

相關問題