时间戳

首页 > 解决方案 > 从左到右的反向链表

c++ - 从左到右的反向链表

问题描述

我收到运行时错误，我不知道为什么。我尝试回溯，但无法弄清楚。请帮忙！

给定的约束：

  1. 列表中的节点数为 n。
  2. 1 <= n <= 500
  3. -500 <= 节点.val <= 500
  4. 1 <= 左 <= 右 <= n

==================================================== =================31==错误：AddressSanitizer：在地址 0x602000000098 在 pc 0x000000370bdd bp 0x7ffdce3742a0 sp 0x7ffdce374298 在 0x60200000098 线程 T0 处读取大小为 8 的堆使用后释放 # 2 0x7fe06dce80b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 0x602000000098 位于 16 字节区域 [0x602000000090,0x60200000090,0x6020000000a0) 内的 8 个字节，此处由线程 T0 释放：#3 0x7fe06dce68b/ -linux-gnu/libc.so.6+0x270b2) 先前由线程 T0 在此处分配：#4 0x7fe06dce80b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 错误地址周围的影子字节：0x0c047fff7fc0： 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7ff0:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff8000：fa fa fd fa fa fd fa fa fa fd fd fa fa fd fd => 0x0c047fff8010：fa fa fd [fd]fa fa fd 00 00 fa fa fd fd 0x0c047fff8020: fa fa fd fd fa fa fd fd fa fa fd fd fa fa fa 0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8050：fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8060：fa fa fa fa fa fa fa fa fa fa fa fa fa fa 影子字节图例（一个影子字节代表 8 个应用程序字节）： 可寻址：00 部分可寻址：01 02 03 04 05 06 07 堆左 redzone：fa 已释放堆区域：fd 堆栈左 redzone：f1 堆栈中 redzone：f2 堆栈右 redzone：f3 返回后堆栈：f5 堆栈使用范围后：f8 全球红区：f9 全局初始化顺序：f6 被用户中毒：f7 容器溢出：fc 数组 cookie：ac Intra object redzone：bb ASan internal：fe Left alloca redzone：ca Right alloca redzone：cb Shadow gap：cc ==31==ABORTING

单链表的定义。

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;
        }
        
        
    }
};

标签： c++data-structureslinked-listruntime-errorsingly-linked-list

解决方案

有几点需要注意：

  • 在取消引用之前检查next引用是否不是空指针。例如： never do head->next->next=，因为您通常不知道是否head->next不是空指针。这是您得到错误的原因。

  • head->next = prev;不会做正确的事，除非反转从第二个节点开始。但在所有其他情况下，这是错误的。您需要对反转部分之前的节点的引用。

  • 您没有涵盖反转从节点 1 开始的情况，因此您需要返回与作为参数的引用不同的引用。

  • 尽管任务描述保证left并且在范围内，但我会在和参数right上添加一些最小的完整性检查。它不会花费超过 2 行代码。leftright

这是建议的解决方案：

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;
    }
}

推荐阅读