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

Question

В настоящее время я пытаюсь сформулировать механизм mergeSort для односвязного списка. Благодаря исследованиям и нахождению согласованных представлений об А) сортировке слиянием, являющейся лучшим способом сортировки односвязных списков, и Б) о том, что это ключевые компоненты для выполнения такой операции, я пришел к следующему коду. Он почти работает точно так, как задумано, но вернет только все целые числа, которые больше последнего введенного числа. Например, ввод 7, 6, 5, 4, 3, 2, 1 вернет 1, 2, 3, 4, 5, 6, 7, а ввод 1, 2, 3, 4, 5 вернет только 5. I Я использовал случайные порядки ввода, поэтому проблема заключается не только в вводе чисел в обратном порядке, но буквально в любом порядке. Если число меньше окончательного, оно удаляется из списка в процессе сортировки. Я не могу найти причину этого вообще. Моя первоначальная проблема была вызвана ошибкой, когда l oop останавливал итерации после одной go, поэтому, как только я удалил, сортировка слиянием работала, но для этой проблемы я только что описал.

Любые советы и предложения приветствуются, и спасибо за ваш вклад. Мои знания о связанных списках и рекурсии не самые большие, поэтому я действительно приветствую любую входную / конструктивную критику здесь.

public Node mergeSort(Node head) {
    if (head == null || head.getNext() == null) return head;
    Node midpoint = findMidpoint(head);
    Node rightliststart = midpoint.getNext();                       
    midpoint.setNext(null);                                                         
    Node rightlist = mergeSort(rightliststart);
    Node sorted = sort(leftlist, rightlist);
    return sorted;
}

public Node findMidpoint(Node head) {                               
    if (head == null) return head;
    Node slowpointer = head;
    Node fastpointer = slowpointer.getNext();
    while (fastpointer != null) {
        fastpointer = fastpointer.getNext();
        if (fastpointer != null) {
            slowpointer = slowpointer.getNext();
            fastpointer = fastpointer.getNext();
        }
    }
    return slowpointer;
}

public Node sort(Node one, Node two) {
    Node temp = null;
    if (one == null) return two;
    if (two == null) return one;
    if (one.getData() <= two.getData()) {
        temp = one;
        temp.setNext(sort(one.getNext(), two));
    } else {
        temp = two;
        temp.setNext(sort(one, two.getNext()));
    }
    return temp;
}

Answer 1

Пример кода слияния. Это показывает, как фиктивный узел используется для упрощения кода (исключается специальный случай обновления заголовка при слиянии первого узла).

    // merge two already sorted lists
    static Node merge(Node list0, Node list1) {
        if(list0 == null)
            return list1;
        if(list1 == null)
            return list0;
        Node temp = new Node();         // dummy node
        Node dest = temp;
        while(true){
            if(list0.data <= list1.data){
                dest.next = list0;
                dest = list0;
                list0 = list0.next;
                if(list0 == null){
                    dest.next = list1;
                    break;
                }
            } else {
                dest.next = list1;
                dest = list1;
                list1 = list1.next;
                if(list1 == null){
                    dest.next = list0;
                    break;
                }
            }
        }
        return temp.next;
    }

Пример кода сортировки слияния сверху вниз. Он сканирует список один раз, чтобы получить размер списка, чтобы избежать двойного сканирования (быстрое, медленное), и сканирует только n / 2 узлов для каждого рекурсивного разбиения.

    // return size of list
    static int size(Node head) {
    int i = 0;
        while(head != null){
            head = head.next;
            i++;
        }
        return i;
    }

    // advance to node n
    static Node advance(Node head, int n) {
        while(0 < n--)
            head = head.next;
        return head;
    }

    // top down merge sort for single link list entry function
    static Node sorttd(Node head) {
        int n = size(head);
        if(n < 2)
            return head;
        head = sorttdr(head, n);
        return head;
    }

    // top down merge sort for single link list recursive function
    static Node sorttdr(Node head, int n) {
        if(n < 2)
            return head;
        int n2 = (n/2);
        Node node = advance(head, n2-1);
        Node next = node.next;
        node.next = null;
        head = sorttdr(head, n2);
        next = sorttdr(next, n-n2);
        head = merge(head, next);
        return head;
    }

Пример кода сортировки слиянием снизу вверх. Он использует небольшой (32) массив списков, где array [i] - это список с 0 (пустой слот) или 2 ^ i узлами. array [{0 1 2 3 4 ...}] = отсортированные подсписки с 0 или {1 2 4 8 16 ...} узлами. Узлы объединяются в массив по одному. Рабочий список создается с помощью последовательности шагов слияния с узлом списка вызывающего и ведущими непустыми слотами в массиве. Размер рабочего списка удваивается с каждым шагом слияния. После того, как каждый непустой слот используется для слияния с рабочим списком, этот слот устанавливается пустым. После выполнения каждой последовательности шагов слияния первый пустой слот после начальных непустых слотов устанавливается в рабочий список. А предыдущие слоты теперь будут пустыми. Как только все узлы объединены в массив, массив объединяется в один отсортированный список. В большом списке, который не помещается в кэш, и с случайно разбросанными узлами, будет много пропусков кэша для каждого доступного узла, и в этом случае сортировка по принципу «снизу вверх» происходит на 30% быстрее, чем сверху вниз.

    // bottom up merge sort for single link list
    static Node sortbu(Node head) {
        final int NUMLIST = 32;
        Node[] alist = new Node[NUMLIST];
        Node node;
        Node next;
        int i;
        // if < 2 nodes, return
        if(head == null || head.next == null)
            return null;
        node = head;
        // merge node into array
        while(node != null){
            next = node.next;
            node.next = null;
            for(i = 0; (i < NUMLIST) && (alist[i] != null); i++){
                node = merge(alist[i], node);
                alist[i] = null;
            }
            if(i == NUMLIST)   // don't go past end of array
                i--;
            alist[i] = node;
            node = next;
        }
        // node == null
        // merge array into single list
        for(i = 0; i < NUMLIST; i++)
            node = merge(alist[i], node);
        return node;
    }