链表的归并排序

Question

Leetcode 上的合并排序代码给出堆栈溢出错误。

ListNode *findMiddle(ListNode *head){
     if (!head) return nullptr;
    ListNode *slow=head;
    ListNode *fast=head;

    while (fast!=nullptr &&  fast->next!=nullptr){
        slow=slow->next;
        fast=fast->next->next;
    }

    return slow;

}

ListNode *merge(ListNode *left,ListNode *right ){
    ListNode *dummy=new ListNode(-1);
    ListNode *tmp=dummy;

    while (left!=nullptr && right !=nullptr){

        if (left->val <right->val){
            tmp->next=left;
            tmp=left;
            left=left->next;
        }

        else {

            tmp->next=right;
            tmp=right;
            right=right->next;
        }
    }

    //remaining arrays 

    if (left) tmp->next=left;
    else tmp->next=right;

    
    ListNode* result = dummy->next;
    delete dummy;

    return result;
}

ListNode* sortList(ListNode* head) {
    
    //base case

    if (head==nullptr || head->next== nullptr ){
        return head;
    }

    ListNode *middle=findMiddle(head);
    ListNode *left=head;
    ListNode *right=middle->next;

    middle->next=nullptr;


    left=sortList(left);
    right=sortList(right);

    return merge(left,right);
}

错误：

第 68 行：第 26 字符： 地址消毒剂：DEADLYSIGNAL =================================================== =============== ==22==错误：AddressSanitizer：地址 0x7ffc38017ff8 上堆栈溢出（pc 0x565014054e8d bp 0x7ffc38018020 sp 0x7ffc38018000 T0）

Answer 1

问题是

findMiddle

返回的节点成为左分区的尾节点。这使得左侧分区始终比右侧分区长。当您从只有两个节点的列表开始时，这是一个真正的问题，因为左侧分区将获得这两个节点，而右侧分区则不会获得其中任何一个。因此，左侧分区上的递归将处于与您已经相同的状态 - 即具有 2 个节点的列表不会被分区到较小的左侧分区中。

以链表

1 → 2

为例。对

findMiddle

的调用以及对

1

的引用将返回对节点

2

的引用。

sortList

将使该节点成为左分区的尾部，将该节点的下一个指针设置为

nullptr

——这已经是

nullptr

，所以没有任何改变。因此，左边的分区也是

1 → 2

，现在你会发现你没有取得任何进展：你被锁定在无限递归中。

要解决此问题，请确保如果在具有偶数个节点的列表上调用

findMiddle

，它将返回对位于前半部分末尾的节点的引用。因此，在

1 → 2

的情况下，它应该返回对节点 1 的引用，而不是节点 2。

要实现此目的，请更改此初始化：

    ListNode *fast=head;

对于这个：

    ListNode *fast=head->next;

通过此更改，它应该按预期工作。