SinglyLinkedList的合并排序似乎会删除任何大于我输入列表的最终数字的数字

Question

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

我们非常欢迎任何建议或建议，并感谢您的任何意见。我对链表和递归的了解并不是最好的，所以我非常欢迎所有的意见/建设性的批评。

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

合并代码示例。这显示了如何使用虚拟节点来简化代码(避免了在合并的第一个节点上更新head的特殊情况(。

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