合并排序链表时出现无限递归错误

Question

我正在链表上应用合并排序。问题是这样的：https://leetcode.com/problems/sort-list/

 void mergesort(ListNode* head,ListNode* low, ListNode* high){
    ListNode* slow = low;
    ListNode* fast = low;
    if (low==high) return;
    while (fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow;
    ListNode* mid1 = mid->next;
    mid->next == NULL;
    mergesort(head,low,mid);
    mergesort(head,mid1,high);
    merge(head,low,mid,high);
}
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* traverse = head;
        while(traverse->next){
            traverse = traverse->next;
        }
        ListNode* high = traverse;
        cout<<high->val;
        ListNode* low = head;
        mergesort(head,low,high);
        return head;
    }
};

我注释掉了合并函数，问题仍然存在，但无论如何，这是合并代码：

void merge(ListNode* head, ListNode* low, ListNode* mid, ListNode* high){
    ListNode* left = low;
    ListNode* right = mid->next;
    ListNode* dummy = new ListNode(-1);
    ListNode* tp = dummy;
    while(right && left!=mid->next){
        if (left->val<right->val){
            dummy->next = left;
            dummy = left;
            left = left->next;
        }
        if (left->val>right->val){
            dummy->next = right;
            dummy = right;
            right = right->next;
        }
    }
    if (right == NULL){
        while (left!=mid->next){
            dummy->next = left;
            left = left->next;
        }
    }
    if (left == mid->next){
        while(right){
            dummy->next = right;
            right = right->next;
        }
    }
    ListNode* start1= tp->next;
    head = start1;
}

我尝试在这里应用合并排序，就像在线性数组上应用合并排序一样。我的试运行表明，事实上已经达到了基本情况（低==高）。然而在编辑器中，它没有达到基本情况。它抛出一些“致命信号错误”：

地址消毒剂：DEADLYSIGNAL

==22==错误：AddressSanitizer：地址 0x7ffc9d343ff8 上堆栈溢出（pc 0x562648afe76b bp 0x7ffc9d344020 sp 0x7ffc9d344000 T0） ==22==正在中止

Answer 1

无限循环的直接原因是你没有断开左右分区之间的链接。你有

mid->next == NULL;

，但那什么也做不了。这应该是一个作业：

mid->next = NULL;

但是除了这个问题之外，还有其他几个问题：

在
```
merge
```
中，您假设
```
right = mid->next;
```
将分配第二个列表的第一个节点，但一旦您解决了上述问题，情况就不是这样了。您刚刚cut两个子列表，因此
```
mid->next
```
始终为空。这也意味着像
```
left!=mid->next
```
这样的条件与说
```
left!=nullptr
```
没有什么不同。您应该将第二个列表的头节点作为参数传递给
```
merge
```
，并让它为
```
right
```
。
由于
```
head
```
是一个按值调用参数，因此对其进行赋值不会影响调用者的同名变量。例如，代码末尾的赋值
```
head=start1
```
是没有用的。因此，调用者将不知道排序列表的第一个节点是什么。您可以通过使用引用调用参数或return头节点引用来解决此问题（我将在下面的解决方案中使用后一个选项）。
```
sortList
```
不适用于处理空列表。它应该检查
```
head
```
为空的情况。
在
```
merge
```
中，当
```
left->val==right->val
```
时会出现无限循环。在这种情况下，循环体不会执行任何操作，因此循环条件将保持不变。与此问题相关的是，当第一个
```
if
```
块在
```
left
```
是该列表的最后一个节点时执行时，第二个
```
if
```
条件可能会命中空指针 (
```
left
```
)。如果您将两个
```
if
```
块组合成一个
```
if ... else
```
结构，那么这两个问题都可以解决。

不是问题，但是：

如果
```
tp
```
是尾指针的缩写，那么你就颠倒了
```
dummy
```
和
```
tp
```
的使用。您的循环前进
```
dummy
```
以引用已排序部分的尾部，同时让
```
tp
```
指向虚拟节点。如果您做了相反的事情，并留下
```
dummy
```
引用虚拟节点，并
```
tp
```
引用尾部，那就更有意义了。
由于您已经有了一个将到达列表末尾的
```
fast
```
指针，因此不需要单独的代码来查找列表的末尾（在
```
sortList
```
中）。相反，只需将一个参数传递给
```
mergeSort
```
，然后让
```
fast
```
帮助您识别列表的尾部（您称之为
```
high
```
）。
在 C++ 中你真的应该使用
```
nullptr
```
而不是
```
NULL
```
在
```
merge
```
结束时，在主循环之后，您不需要另一个循环来附加剩余的节点。只需将剩余部分链接到已排序部分的尾部就足够了。此后的所有下一个链接都不必更改。
```
merge
```
不使用
```
high
```
参数，也不需要它。

这是您的代码，考虑并纠正了上述所有内容：

// No need for unused head and high parameters; but return the node that becomes head
ListNode* merge(ListNode* left, ListNode* right) {
    // Note that the two given lists are disjoint: mid1->next is nullptr.
    ListNode* dummy = new ListNode(-1);
    ListNode* tp = dummy;
    while (right && left) {
        if (left->val < right->val){
            tp->next = left;
            tp = left; // tp is the tail of the sorted part
            left = left->next;
        } else { // Must be an ELSE block (mutually exclusive) 
            tp->next = right;
            tp = right;
            right = right->next;
        }
    }
    if (right == NULL) {
        // No need for a loop here: just attach the remainder:
        tp->next = left;
    } else { // Can be an ELSE block
        tp->next = right;
    }
    // Assigning to `head` serves no purpose (`head` was a call-by-value parameter)
    return dummy->next; // Instead: return the head of the sorted list
}

// No need for three parameters; but return the new head
ListNode* mergesort(ListNode* head){
    if (!head->next) return head; // Adapated condition (no need for high)
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* high = fast->next ? fast->next : fast; // Define high
    ListNode* mid = slow;
    ListNode* mid1 = mid->next;
    mid->next = nullptr; // Assign! And don't use NULL in C++
    head = mergesort(head); // Get the first node back
    mid1 = mergesort(mid1); // (idem)
    return merge(head, mid1); // Return the first node of the result
}


class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        // No need to get the tail node here
        return mergesort(head); // Return the new head
    }
};

合并排序链表时出现无限递归错误

问题描述投票：0回答：1

1个回答

最新问题

合并排序链表时出现无限递归错误

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1