从左到右的反向链表

Question

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

给定的限制条件：

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

================================================================= ==31==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000098 at pc 0x000000370bdd bp 0x7ffdce3742a0 sp 0x7ffdce374298 READ of size 8 at 0x602000000098 thread T0 #2 0x7fe06dce80b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 0x602000000098 is located 8 bytes inside of 16-byte region [0x602000000090,0x6020000000a0) freed by thread T0 here: #3 0x7fe06dce80b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) previously allocated by thread T0 here: #4 0x7fe06dce80b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) Shadow bytes around the buggy address: 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 fa fd fa fa fa fd fd fa fa fd fd =>0x0c047fff8010: fa fa fd[fd]fa fa fd fd fa fa 00 00 fa fa fd fd 0x0c047fff8020: fa fa fd fd fa fa fd fd fa fa fd fd fa fa fa fa 0x0c047fff8030: fa fa 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 fa fa fa fa fa 0x0c047fff8050: fa fa fa 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 fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array 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;
        }
        
        
    }
};

Answer 1

所以你的问题是，你引用了一个先前的节点并创建了一个循环，而其他一些节点仍然位于你的内存中但不再在代码中解决。通常垃圾收集器会清理它，但在 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 已经被反转它将 return 错误的节点。

这是你添加了anker的代码，你的反向算法工作正常，我稍微调整了after逻辑，现在它应该工作正常了。

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

如果您想反转整个列表，您的逻辑仍然会失败。

希望我能帮到你，解释清楚。

Answer 2

有几点需要注意：

在取消引用之前检查 next 引用是否不是空指针。例如：永远不要做 head->next->next=，因为您通常不知道 head->next 是否不是空指针。这是您收到错误的原因。
head->next = prev;不会做正确的事情，除非反转从第二个节点开始。但在所有其他情况下，这是错误的。您需要对反转部分之前的节点的引用。
您没有涵盖反转从节点 1 开始的情况，因此您需要 return 与您作为参数获得的参考不同的参考。
虽然任务描述保证 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;
    }
}

从左到右的反向链表

Reverse linked list from position left to right

c++

runtime-error

linked-list

data-structures

singly-linked-list