Сортировать список ссылок с помощью Merge Sort в Java

Question

Я пытаюсь реализовать сортировку слиянием в Linkedin List. Это приводит к ошибке StackOverflowError. Ниже приводится реализация, сделанная мной. Пожалуйста, скажите мне, какие изменения должны быть сделаны.

public class Solution {
    public ListNode sortList(ListNode A) {
        if (A == null || A.next == null)
        {
            return A;
        }
        ListNode middle = getMiddle(A);
        ListNode middleNext = middle.next;
        middle.next = null;
        ListNode left = sortList(A);
        ListNode right = sortList(middleNext);
        ListNode head = combine(left,right);
        return head;
    }

    public ListNode combine(ListNode head,ListNode otherHead){
        ListNode combineResult = null;
        if(head==null)
            return otherHead;
        if(otherHead == null)
            return head;
        if(head.val<=otherHead.val){
            combineResult = head;
            combineResult.next = combine(head.next,otherHead);
        } else {
            combineResult = otherHead;
            combineResult.next = combine(head,otherHead.next);
        }
        return combineResult;
    }

    public ListNode getMiddle(ListNode A){
        ListNode fastPtr = A;
        ListNode slowPtr = A;
        while(fastPtr!=null && fastPtr.next!=null){
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
        return slowPtr;
    }
}

Answer 1

У вас есть объявление этого метода

public ListNode sortList(ListNode A) {

и без каких-либо изменений на A, вы вызываете метод следующим образом:

ListNode left = sortList(A);

Поскольку у вас нет знака конца, выиметь бесконечную рекурсивность.Ввод sortList должен быть самым левым и самым правым узлом вашего текущего интервала, и, так как у вас есть связанный список, количество элементов в интервале не повредит ни как параметр, чтобы избежать необходимости повторного вычисления,Теперь вместо этого у вас есть один параметр, ListNode, который называется A.Этого недостаточно для определения интервала.

Идея сортировки слиянием состоит в том, чтобы многократно делить упорядоченный набор на две половины, разбивать его, ставить похожие, но более простые подзадачи, пока мы не достигнем тривиальности и не решим тривиальные задачи, а затемСочетание таких тривиальных задач становится проще.