从左到右反转链表

我得到运行时错误，我不知道为什么。我试着回溯，但没能搞清楚。请帮忙！

限制条件：

列表中的节点数为n
1<=n<=500
-500<=Node.val<=500
1<=left<=右<=n

====================================================================31===错误：AddressSanitizer：在pc 0x000000370bdd bp 0x7ffdce3742a0 sp的地址0x602000000098上释放后堆使用0x7ffdce374298在0x602000000098线程T0读取大小为8#2 0x7fe06dce80b2(/lib/x86_64-linux-gnu/libc.so.6+0x270b2(0x602000000098位于16字节区域内的8个字节[0x6000000090,0x6000000a0(此处由线程T0释放：#3 0x7fe06dce80b2(/lib/x86_64-linux-gnu/libc.so.6+0x270b2(先前由线程T0在此处分配的：#4 0x7fe06dce80b2(/lib/x86_64-linux-gnu/libc.so.6+0x270b2(错误地址周围的阴影字节：0x0c047fff7fc0:00 00 00 000x0c047fff7fd0:00 00 00 000x0c047fff7fe0:00 00 00 000x0c047fff7ff0:00 00 00 000x0c047fff8000:fa fa fd fa fa fd=>0x0c047fff8010:fa fa fd[fd]fa fa fd fd fa fa 00 fa fd fd0x0c047fff8020:fa fa fd fd fa fd fa fd0x0c047fff8030:fa fa fa fa0x0c047fff8040:fa fa fa fa0x0c047fff8050:fa fa fa fa0x0c047fff8060:fa fa fa fa阴影字节图例(一个阴影字节表示8个应用程序字节(：可寻址：00部分可寻址：01 02 03 04 05 06 07堆左侧红区：fa空闲堆区域：fd堆栈左侧红区：f1堆栈中间红区：f2堆叠右侧红区：f3返回后堆栈：f5作用域之后的堆栈使用：f8全局红区：f9全局初始化顺序：f6用户中毒：f7容器溢出：fc数组cookie：ac对象内部红区：bbA内部：fe左分配红区：ca右侧分配红区：cb阴影间隙：cc===31===中止

单链表的定义。

struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *h=head;
if(left!=right) {
for(int i=1;i<left-1;++i) 
{
h=h->next;
}
ListNode *fr=NULL;
ListNode *prev=h;
h=h->next;
for(int j=left;j<=right;++j)
{
fr=h->next;
h->next=prev;
prev=h;
h=fr;
}
head->next->next=prev->next;
head->next=prev;
//h=prev;
return head;
}
else {
return head;
}


}
};

需要注意以下几点：

在取消引用next之前，请检查它是否不是空指针。例如：永远不要执行head->next->next=，因为您通常不知道head->next是否不是空指示器。这就是您出现错误的原因。
head->next = prev;不会做正确的事情，除非反转从第二个节点开始。但在所有其他情况下，这都是错误的。您需要对反转的节之前的节点的引用。
您没有涵盖反转从节点1开始的情况，因此您需要返回与作为参数获得的引用不同的引用。
尽管任务描述保证left和right在范围内，但我会对left和right参数添加一些最小健全性检查。它的代码成本不超过2行。

以下是建议的解决方案：

ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left < 1) left = 1;
if (!head || left >= right) return head;
ListNode *h = head;
for (int i = 1; i < left - 1; ++i) {
h = h->next;
if (!head) return head;
}
ListNode *prev = left > 1 ? h->next : h;
if (!prev) return head;
ListNode *unmoved = left > 1 ? h : nullptr;
ListNode *moved = prev;
h = prev->next;
for (int j = left + 1; j <= right && h; ++j) {
ListNode * fr = h->next;
h->next = prev;
prev = h;
h = fr;
}
moved->next = h;
if (unmoved) {
unmoved->next = prev;
return head;
} else {
return prev;
}
}

因此，您的问题是，您引用了上一个节点并创建了一个循环，而其他一些节点仍然位于内存中，但不再在代码中进行处理。通常垃圾收集器会清理这些，但在C++中，您必须自己管理内存分配。

我稍微调整了一下你的逻辑，以防止它产生循环(变量被重命名(

ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* current = head;
if (left != right) {
for (int i = 1; i < left - 1; ++i)
{
current = current->next;
}

ListNode* ankerLeft = left == 1 ? nullptr : current;
ListNode* ankerRight = current->next;

ListNode* nextNode = nullptr;
ListNode* prevNode = ankerRight;

for (int j = left-1; j <= right; ++j)
{
if (current != nullptr) {
nextNode = current->next;
current->next = prevNode;
prevNode = current;
current = nextNode;
}
}
if (ankerLeft != nullptr) {
ankerLeft->next = prevNode;
ankerRight->next = current;
}
else {
head->next = current;
head = prevNode;
}
return head;
}
else {
return head;
}
}

这也使得现在可以反转整个列表。(感谢@dratenik的评论(

这对我来说很好，不应该让你失去任何保留的内存

编辑：

在仔细阅读了您的逻辑之后，您唯一缺少的是对反向列表的最后一个节点的引用，以便再次正确连接到原始列表head->next->next = prev->next;不会给你正确的节点，因为你已经覆盖了节点，我在你的代码中包含了一个anker，以保留对反向算法最后一个节点的引用。此外，prev->next是错误的节点，因为prev->next已经被反转，它将返回错误的节点。

这是添加了anker的代码，你的反向算法运行良好，我调整了一点后逻辑，现在它应该运行良好。

ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* h = head;
if (left != right) {
for (int i = 1; i < left - 1; ++i)
{
h = h->next;
}
ListNode* fr = NULL;
ListNode* prev = h;
ListNode* ankerRight = h->next;
h = h->next;
for (int j = left; j <= right; ++j)
{
fr = h->next;
h->next = prev;
prev = h;
h = fr;
}
// this would overwrite the wrong reference and create a loop
// head->next->next = prev->next;
head->next = prev;
ankerRight->next = h;
return head;
}
else {
return head;
}
}

如果你想颠倒整个列表，你的逻辑仍然会失败。

希望我能帮上忙，解释清楚。

相关内容

最新更新

热门标签：