单链表的合并排序似乎删除了任何大于我输入到列表中的最终数字的数字

Question

我目前正在尝试为单链表制定一个mergeSort机制。通过研究并找到关于 A) 合并排序是对单向链表进行排序的最佳方式，以及 B) 这些是执行此类操作的关键组件的一致想法，我得出了以下代码。它几乎完全按预期工作，但只会 return 所有大于最后输入数字的整数。比如输入7,6,5,4,3,2,1会return1,2,3,4,5,6,7,但是输入1,2,3,4,5只会return 5. 我使用的是随机输入顺序，所以这不是仅以相反顺序输入数字的问题，而是任何顺序。如果一个数字小于最终数字，它将在排序过程中从列表中删除。我根本找不到原因。我最初的问题是由一个错误的 while 循环引起的，该循环一次就停止了迭代，所以一旦我删除了合并排序就可以工作，但是对于我刚刚描述的这个问题。

我们非常欢迎您提出任何意见或建议，并感谢您提供的任何意见。我对链表和递归的了解不是最好的，所以我非常欢迎大家input/constructive批评。

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;
    }

单链表的合并排序似乎删除了任何大于我输入到列表中的最终数字的数字

Merge Sort for Singly Linked List seems to remove any numbers larger than the final number I input into the list

mergesort

linked-list