0

我正在尝试使用 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;
}

谁能告诉我为什么会这样？非常感谢！

4

3 回答 3

0

我认为您的反向算法是正确的，但是remain是一个局部变量，返回后无效，因此 L4 将包含无效指针。reverse()更改取回的签名List *。

列表 *reverse(列表 *L){
    if(L->next == NULL) 返回 L;
    列表 *remain = reverse(L->next);
    列表 *当前 = 剩余；
    而（当前->下一个！= NULL）
        当前=（当前->下一个）；
    L->下一个 = NULL；
    当前->下一个 = L；
    //打印（保留）；
    返回剩余；
}
于 2012-09-03T02:27:25.487 回答
0

只需查看您的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-03T05:29:01.020 回答
0

首先，我想向您指出，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

所以返回值为 L 的位置的 a 在逻辑上是不正确List的next，

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

这会在您的实现中导致未定义的行为。

编辑：我有一些空闲时间，所以我想出了这个实现。尽管修改了调用它的原始列表，但它使用相同的算法。

于 2012-09-03T06:05:24.313 回答