我正在解决算法问题,我必须反转一个正向链表。下面是我的代码:对于节点:
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;
}
1条答案
按热度按时间mm9b1k5b1#
让我们看看你的代码:
这段代码将永远不会打印头。稍微好一点的代码应该是:
现在,从
main
中的代码来看,您似乎并不期望打印head --而是将其用作指针。这会很奇怪。您基本上有一个额外的空节点挂在外面。因此,您的main
可以这样做:最后,你的reverse方法彻底崩溃了,你不应该分配任何东西。
链表和其他形式的链接结构(如树)可能会非常令人困惑。在你学习的这个阶段,画图真的很有帮助。我这样做了很多年,当它变得复杂时,我仍然这样做。
可能有一个更优雅的方法来做到这一点,但我不想想去想那么难:-)
想一想这个函数的作用,它跟踪前一个节点,第一次循环时,没有前一个节点,之后,前一个节点是旧头,然后是旧头-〉下一个,等等。
在每一个节点上,它设置了指向前一个节点的next指针,所以head-〉next变成了nullptr(这是列表的新结尾),Old Head-〉next-〉next变成了old head,等等。
我没有测试过这个代码。
这是我的最终版本,包含编译和输出: