Блог

Итак, я пытаюсь отсортировать этот связанный список, я понимаю каждую часть кода, кроме этого небольшого фрагмента, в функции 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 resu< 
    } 

    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 
  

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

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

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

Итак, если вы видите весь код целиком, 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, amp;a, amp;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 половины и сортирует их по отдельности, вызывая один и тот же метод. Для достижения того же самого сначала копируется следующее значение в nextofmiddle и они делают middle.next = null; , чтобы прервать цикл рекурсии.

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

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

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

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