使用合并排序对链接列表进行排序时得到错误的答案

Question

我尝试编写自定义版本的合并排序，其中 sortList 函数是递归的，但合并函数是迭代的。

我试过dry运行但无法找出问题所在

这是一个自定义测试用例，也会导致错误答案。

Your input:
5 4 3 1 2 6
Your function returned the following: 
1 -> 2 -> 3 -> 6

Link 问题：https://www.interviewbit.com/problems/sort-list/

完整代码：

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/

ListNode* Solution::sortList(ListNode* A) {

    ListNode * head = A;

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

    ListNode * slow = head, * fast = head;

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

    ListNode * temp = slow->next;

    slow->next = NULL;

    head = sortList(head);
    temp = sortList(temp);
    ListNode * ptr;
    ListNode * ans;

    ans = head->val > temp->val ? temp : head;

    while(head!=NULL && temp!=NULL)
    {
        if(head->val > temp->val){
            ptr = temp;
            temp = temp->next;
            ptr->next = head;
        }else
        {
            ptr = head;
            head = head -> next;
            ptr->next = temp;
        }
    }
    
    return ans;
}

Answer 1

我试图实现的合并功能是错误的。

这是正确的代码。

ListNode* Solution::sortList(ListNode* A) {

    ListNode * head = A;

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

    ListNode * slow = head, * fast = head;

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

    ListNode * temp = slow->next;

    slow->next = NULL;

    head = sortList(head);
    temp = sortList(temp);

    ListNode * ans = new ListNode(0);

    ListNode * realAns = ans;

    while(head!=NULL && temp!=NULL)
    {
        if(head->val > temp->val)
        {
            ans->next = temp;
            temp = temp->next;
        }else{
            ans->next = head;
            head = head->next;
        }

        ans = ans->next;
    }
    
    if(temp==NULL && head!=NULL)
    {
        ans->next = head;
    }else if(temp!=NULL && head==NULL)
    {
        ans->next = temp;
    }

    return realAns->next;
}

使用合并排序对链接列表进行排序时得到错误的答案

Getting wrong answer for sorting linked list using merge sort

c++

mergesort

linked-list