链表c++倒排算法中删除结点的问题

mi7gmzs6  于 2023-02-14  发布在  其他
关注(0)|答案(1)|浏览(129)

我正在解决算法问题,我必须反转一个正向链表。下面是我的代码:对于节点:

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

下面是我做的反转算法:

Node* reverse(Node* head){
    Node* node = head->next;
    Node* sentry = new Node;
    sentry->next = head;
    while(node != nullptr){
        head->next = node->next;
        node->next = sentry->next;
        sentry->next = node;
        node = head->next;
    }
    return sentry;
}

下面是一个要测试的打印函数:

void print(Node* head){
    Node* node = head->next;
    while(node != nullptr){
        std::cout << node->value << '-';
        node = node->next;
    }
}

问题是,倒排表的最后一个节点是头节点,所以当我尝试这样做时:delete head;之前return sentry;删除该节点我得到核心转储错误。我知道我可以在互联网上搜索一个方法来反转列表,但我想了解为什么会发生这种情况,为什么我不能只是删除头节点。
编辑:下面是删除head的代码:

Node* reverse(Node* head){
    Node* node = head->next;
    Node* sentry = new Node;
    sentry->next = head;
    while(node != nullptr){
        head->next = node->next;
        node->next = sentry->next;
        sentry->next = node;
        node = head->next;
    }
    delete head; // head = nullptr; also doesn't work.
    return sentry;
}

下面是要测试的主要函数:

int main(){
    Node* node5 = new Node{5,nullptr};
    Node* node4 = new Node{4,node5};
    Node* node3 = new Node{3,node4};
    Node* node2 = new Node{2,node3};
    Node* node1 = new Node{1,node2};
    Node* head = new Node;
    head->next = node1;
    head->value;
    print(reverse(head));
    return 0;
}
mm9b1k5b

mm9b1k5b1#

让我们看看你的代码:

void print(Node* head){
    Node* node = head->next;
    while(node != nullptr){
        std::cout << node->value << '-';
        node = node->next;
    }
}

这段代码将永远不会打印头。稍微好一点的代码应该是:

void print(Node* head) {
    for (Node * node = head; node != nullptr; node = node->next) {
        std::cout << node->value << '-';
    }
}

现在,从main中的代码来看,您似乎并不期望打印head --而是将其用作指针。这会很奇怪。您基本上有一个额外的空节点挂在外面。因此,您的main可以这样做:

int main(){
    Node* node5 = new Node{5,nullptr};
    Node* node4 = new Node{4,node5};
    Node* node3 = new Node{3,node4};
    Node* node2 = new Node{2,node3};
    Node* head = new Node{1,node2};

    std::cout << "Original version: ";
    print(head);
    std::cout << "\n\n";

    std::cout << "Reversed version: ";
    print(reverse(head));
    std::cout << "\n";

    return 0;
}

最后,你的reverse方法彻底崩溃了,你不应该分配任何东西。
链表和其他形式的链接结构(如树)可能会非常令人困惑。在你学习的这个阶段,画图真的很有帮助。我这样做了很多年,当它变得复杂时,我仍然这样做。

Note * reverse(Node *head) {
    Node * prev = nullptr;

    while (head != nullptr) {
        Node * nextNode = head->next;

        head->next = prev;
        prev = head;
        head = nextNode;
    }

    return prev;
}

可能有一个更优雅的方法来做到这一点,但我不想想去想那么难:-)
想一想这个函数的作用,它跟踪前一个节点,第一次循环时,没有前一个节点,之后,前一个节点是旧头,然后是旧头-〉下一个,等等。
在每一个节点上,它设置了指向前一个节点的next指针,所以head-〉next变成了nullptr(这是列表的新结尾),Old Head-〉next-〉next变成了old head,等等。
我没有测试过这个代码。
这是我的最终版本,包含编译和输出:

^ make Foo && Foo
g++     Foo.cpp   -o Foo
Original: 1 : 2 : 3 : 4 : 5 : 

Reversed: 5 : 4 : 3 : 2 : 1 : 

^ cat Foo.cpp
#include <iostream>

struct Node{
    Node (int v): value(v) {}

    int value = 0;
    Node* next = nullptr;
};

void print(Node* head);
Node * reverse(Node* head);

int main() {
    // This part is gross, but I was in a hurry
    Node * head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    std::cout << "Original: ";
    print(head);
    std::cout << "\n\nReversed: ";
    print(reverse(head));
    std::cout << "\n";
}

void print(Node* head) {
    for (Node * node = head; node != nullptr; node = node->next) {
        std::cout << node->value << " : ";
    }
}

Node * reverse(Node *head) {
    Node * prev = nullptr;

    while (head != nullptr) {
        Node * nextNode = head->next;

        head->next = prev;
        prev = head;
        head = nextNode;
    }

    return prev;
}

相关问题