병합 정렬을 사용하여 연결 목록 정렬에 대한 오답 얻기 (Getting wrong answer for sorting linked list using merge sort)

문제 설명

병합 정렬을 사용하여 연결 목록 정렬에 대한 오답 얻기 (Getting wrong answer for sorting linked list using merge sort)

sortList 함수는 재귀적이지만 병합 함수는 반복적인 병합 정렬의 사용자 지정 버전을 작성하려고 했습니다.

건식 실행을 시도했지만 문제를 파악할 수 없었습니다.

이것은 또한 오답이 나오는 커스텀 테스트 케이스입니다.

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

질문 링크: 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;

}

</code></pre>





참조 솔루션
방법 1:
 
The merge function I was trying to implement was wrong.

Here is the correct code.

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;
}
(by AtharvaU、AtharvaU)
참조 문서


Getting wrong answer for sorting linked list using merge sort (CC BY‑SA 2.5/3.0/4.0)