Почему middle.next имеет значение null?

Question

Итак, я пытаюсь отсортировать этот связанный список, я понимаю каждую часть кода, кроме этого маленького кусочка, под функцией mergeSort, строка 9. Почему для middle.next должно быть установлено значение null?Я не вижу, что это делает, что необходимо?

Вот ссылка на то, откуда я получил код (под кодом примера Java):

https://www.geeksforgeeks.org/merge-sort-for-linked-list/

Вот код:

// Java program to illustrate merge sorted 
// of linkedList 

public class linkedList { 
    node head = null; 
    // node a, b; 
    static class node { 
        int val; 
        node next; 

        public node(int val) { 
            this.val = val; 
        } 
    } 

    node sortedMerge(node a, node b) { 
        node result = null; 
        /* Base cases */
        if (a == null) 
            return b; 
        if (b == null) 
            return a; 

        /* Pick either a or b, and recur */
        if (a.val <= b.val) { 
            result = a; 
            result.next = sortedMerge(a.next, b); 
        } else { 
            result = b; 
            result.next = sortedMerge(a, b.next); 
        } 
        return result; 
    } 

    node mergeSort(node h) { 
        // Base case : if head is null 
        if (h == null || h.next == null) { 
            return h; 
        } 

        // get the middle of the list 
        node middle = getMiddle(h); 
        node nextofmiddle = middle.next; 

        // set the next of middle node to null 
        middle.next = null; 

        // Apply mergeSort on left list 
        node left = mergeSort(h); 

        // Apply mergeSort on right list 
        node right = mergeSort(nextofmiddle); 

        // Merge the left and right lists 
        node sortedlist = sortedMerge(left, right); 
        return sortedlist; 
    } 

    // Utility function to get the middle of the linked list 
    node getMiddle(node h) { 
        // Base case 
        if (h == null) 
            return h; 
        node fastptr = h.next; 
        node slowptr = h; 

        // Move fastptr by two and slow ptr by one 
        // Finally slowptr will point to middle node 
        while (fastptr != null) { 
            fastptr = fastptr.next; 
            if (fastptr != null) { 
                slowptr = slowptr.next; 
                fastptr = fastptr.next; 
            } 
        } 
        return slowptr; 
    } 

    void push(int new_data) { 
        /* allocate node */
        node new_node = new node(new_data); 

        /* link the old list off the new node */
        new_node.next = head; 

        /* move the head to point to the new node */
        head = new_node; 
    } 

    // Utility function to print the linked list 
    void printList(node headref) { 
        while (headref != null) { 
            System.out.print(headref.val + " "); 
            headref = headref.next; 
        } 
    } 

    public static void main(String[] args) { 

        linkedList li = new linkedList(); 
        /* 
         * Let us create a unsorted linked list to test the functions 
         * created. The list shall be a: 2->3->20->5->10->15 
         */
        li.push(15); 
        li.push(10); 
        li.push(5); 
        li.push(20); 
        li.push(3); 
        li.push(2); 

        // Apply merge Sort 
        li.head = li.mergeSort(li.head); 
        System.out.print("\n Sorted Linked List is: \n"); 
        li.printList(li.head); 
    } 
} 

// This code is contributed by Rishabh Mahrsee 

Answer 1

Цель middle.next = null - разбить список на две части.Значение после последнего узла в связанном списке всегда должно быть NULL, поэтому автор установил для узла next узла middle значение NULL.Автор создает один подсписок, содержащий узлы от head до middle, и второй подсписок, содержащий узлы от nextofmiddle до конца списка.Каждый раз, когда вызывается эта функция, подсписок разбивается на более мелкие части, что является частью процесса сортировки слиянием.

Answer 2

mergeSort устанавливает для next члена среднего узла значение null, чтобы разбить список h на 2 отдельных списка h и nextofmiddle, которые он сортирует, вызывая себя рекурсивно, а затем объединяет для полученияsortedList.

Обратите внимание, однако, что этот код имеет серьезную проблему: метод sortedMerge также рекурсивен с глубиной стека объединенной длины обоих списков, потенциально большим числом.Эта рекурсия не может быть легко упрощена компилятором как хвостовая рекурсия, поэтому сортировка длинных списков с этим кодом, вероятно, приведет к сбою.

Answer 3

Похоже, что автор ищет среднюю точку списка в методе node getMiddle(node h).Это возвращает средний узел, но вы хотите разбить список на две части: левую и правую стороны.

Установка middle.next = null разбивает список на две части.

Answer 4

Это разделить список на две части: когда средний элемент найден, первая часть заканчивается на среднем элементе, поэтому middle.next устанавливается в ноль. Предыдущее значение middle.next является началом второй части.

Answer 5

Таким образом, если вы видите весь код, mergeSort() вызывается рекурсивно,

 // Apply mergeSort on left list 
    node left = mergeSort(h); 

 // Apply mergeSort on right list 
    node right = mergeSort(nextofmiddle); 

И, помещая middle.next = null, он фактически прерывает рекурсию вызывающего метода в стеке методов.Таким образом, он вернет текущий узел, когда мы рекурсивно вызовем тот же метод,

if (h == null || h.next == null) { 
    return h; 
}

Так что, если вы видите код psedo,

MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List 
   then return.
2) Else divide the linked list into two halves.  
   FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
    MergeSort(a);
    MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here) 
   and update the head pointer using headRef.
   *headRef = SortedMerge(a, b);

Это фактически разбивает список на 2 половины иПо отдельности MergeSort их вызывает тот же метод.Чтобы добиться того же, сначала скопируйте следующее значение в nextofmiddle, и они заставят middle.next = null; разорвать цикл рекурсии.

Надеюсь, это прояснит ваше сомнение.