所以Natural mergeSort是mergeSort的一种变体，您无需遍历列表，而是遍历列表，创建2个“自然排序”的新临时列表，然后对这2个列表进行排序。例如列表= 1、3、2、4、5，空
<因为1 <3，但3不是<2第二临时列表== 2，4，5
下一步是将第一临时列表与第二临时列表进行比较if( firstTemp > secondTemp)
swap;
我的问题来自创建这两个单独的列表。当我创建2个新列表时，它会删除我的原始列表。同样，我似乎无法正确地创建列表的大小。新列表似乎不像新列表那样工作，因为计数器不断从原始列表增加到新列表。像以上，然后firstTemp.size = 7secondTemp.size = 10何时应该ogList.size = 5
和secondTemp.size = 3firstTemp.size = 2
package mergesortlinkedlist;
public class MergeSortLinkedList {
static LinkedList list = new LinkedList();
public static void main(String[] args) {
//
// start linked list
//
LinkedList.push(list, 1);
LinkedList.push(list, 3);
LinkedList.push(list, 2);
LinkedList.push(list, 4);
LinkedList.push(list, 5);
list.printList(list);
System.out.println("list size = " + list.head.getCounter());
naturalMerge(list);
}
public static void naturalMerge(LinkedList front) {
LinkedList set1 = new LinkedList();
LinkedList set2 = new LinkedList();
LinkedList temp = front;
//get first temp list
while (temp != null) {
if (temp.head.data < temp.head.next.data) {
LinkedList.push(set1, temp.head.data);
temp.head = temp.head.next;
} else {
LinkedList.push(set1, temp.head.data);
temp.head = temp.head.next;
break;
}
}
//get second temp list
while (temp != null) {
if (temp.head.data < temp.head.next.data) {
LinkedList.push(set2, temp.head.data);
temp.head = temp.head.next;
} else {
LinkedList.push(set2, temp.head.data);
temp.head = temp.head.next;
break;
}
}
mergeSwap(set1, set2);
}
public static void mergeSwap(LinkedList set1, LinkedList ){
//template code to swap the naturally sorted temp lists
}
}
}
public class LinkedList {
public Node head;
public static class Node {
public Node next = null;
public Integer data;
public static int counter = 0;
Node() {
}
Node(int d) {
this.data = d;
}
public void setCounter(int n) {
counter += n;
}
public int getCounter() {
return counter;
}
}
public static void push(LinkedList list, int data) {
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
new_node.setCounter(1);
} else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
new_node.setCounter(1);
}
// Return the list by head
//return list;
}
我只是想知道我的这段代码是否可以为自然mergeSort创建单独的列表。我可以使用此代码创建新列表而不破坏原始列表吗？最终，我希望我的列表= 1,2,3,4,5，null
naturalMerge(list);
交换节点后，我从main完成。唯一的原因是因为某种原因我得到了空指针异常。我想回到这一点并使它更好地工作，但是现在它可能会完成我的任务。
package mergesortlinkedlist; public class MergeSortLinkedList { // static Node first = new Node(); static LinkedList list = new LinkedList(); public static void main(String[] args) { // start linked list list.add(list, 1); list.add(list, 5); list.add(list, 3); list.add(list, 4); list.add(list, 2); list.add(list, 100); list.add(list, 76); list.add(list, -6); list.printList(list); naturalMerge(list); list.printList(list); naturalMerge(list); list.printList(list); naturalMerge(list); list.printList(list); } public static void naturalMerge(LinkedList front) { LinkedList set1 = new LinkedList(); LinkedList set2 = new LinkedList(); LinkedList temp = front; int size1 = 0; int sortCounter = 0; //if sortCounter != 0, then there is more to sort //get first temp list while (temp.head.data != null) { if (temp.head.data < temp.head.next.data) { set1.add(set1, temp.head.data); size1++; temp.head = temp.head.next; } else { set1.add(set1, temp.head.data); size1++; temp.head = temp.head.next; break; } } //get second temp list while (temp.head != null) { if (temp.head.next == null) { set2.add(set2, temp.head.data); temp.head = temp.head.next; break; } if (temp.head.data < temp.head.next.data) { set2.add(set2, temp.head.data); temp.head = temp.head.next; } else { set2.add(set2, temp.head.data); temp.head = temp.head.next; break; } } mergeSwap(set1, set2, size1); } public static void mergeSwap(LinkedList set1, LinkedList set2, int size1) { System.out.println(); LinkedList temp = set1; LinkedList temp2 = set2; while (temp.head != null && temp2.head != null) { if (temp.head.data < temp2.head.data) { list.add(list, temp.head.data); temp.head = temp.head.getNext(); //increment temp } else { list.add(list, temp2.head.data); temp2.head = temp2.head.getNext(); //increment temp2 } //if one list is empty, break loop and add remaining nodes if (temp.head == null || temp2.head == null) { break; } } //check which list is empty, and add the remaining nodes to original list if (temp.head == null) { while (temp2.head != null) { list.add(list, temp2.head.data); temp2.head = temp2.head.getNext(); } } else { while (temp.head != null) { list.add(list, temp.head.data); temp.head = temp.head.getNext(); } } //naturalMerge(list); //this call breaks the code, but why? How is it any different from the method call in main? } }