class Node {
int data;
Node next;
public Node(int a) {data = a; next = null;}
}
public class List {
public Node head;
public List() {
head = null;
}
public boolean isEmpty() {
return head == null;
}
public void insertAtFront(int a) {
Node node = new Node(a);
node.next = head;
head = node;
}
public void insertAtEnd(int a) {
Node node = new Node(a);
// this check cannot be omitted
// otherwise you get NullPointerException on an empty list.
if (head == null) {
insertAtFront(a);
return;
}
Node cur = head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
public void insertAfter(Node node, int a) {
Node newNode = new Node(a);
if (node == null) {
System.out.println("Oops...");
return;
}
newNode.next = node.next;
node.next = newNode;
}
public Node search(int a) {
Node cur = head;
while(cur != null && cur.data != a) cur = cur.next;
return cur;
}
public int deleteFirst() {
if (head == null) {
System.out.println("Oops...");
return -1;
}
Node node = head;
head = head.next;
node.next = null;
return node.data;
}
public int deleteLast() {
if (head == null || head.next == null)
return deleteFirst();
Node second = head;
Node cur = second.next;
// when the thile loop finishes,
// cur points to the last node.
while(cur.next != null) {
second = cur;
cur = cur.next;
}
second.next = null;
return cur.data;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node cur = head;
while(cur != null) {
sb.append(cur.data);
if (cur.next != null) sb.append(", ");
cur = cur.next;
}
return sb.toString();
}
private Node merge(Node head1, Node head2) {
Node dummy = new Node(0);
Node tail = dummy;
while (head1 != null && head2 != null) {
if (head1.data < head2.data) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
if (head1 != null) {
tail.next = head1;
} else {
tail.next = head2;
}
return dummy.next;
}
public Node mergesort(Node head) {
if (head == null || head.next == null) {
return head;
}
Node mid = findMiddle(head);
Node right = mergesort(mid.next);
mid.next = null;
Node left = mergesort(head);
return merge(left, right);
}
private Node findMiddle(Node head) {
Node slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public static void main(String[] args) {
List list = new List();
list.insertAtFront(37);
list.insertAtFront(99);
list.insertAtFront(12);
// the list at page 88 of the slides.
System.out.println(list);
list.insertAtFront(75);
System.out.println(list);
list.insertAtEnd(38);
System.out.println(list);
list.insertAfter(list.search(12), 85);
System.out.println(list);
list.mergesort(list.head);
System.out.println("after sorting: " + list + "\n");
System.out.println("delete the first, which is " + list.deleteFirst());
System.out.println(list);
System.out.println("delete the last, which is " + list.deleteLast());
System.out.println(list);
}
}
Вот мой код для связанного списка в сортировке слияния. Однако была показана только задняя часть связанного списка. в чем проблема....?Неожиданный результат в Merge Сортировать по указанному списку (JAVA)
Использование Intellij:
12, 99, 37
75, 12, 99, 37
75, 12, 99, 37, 38
75, 12, 85, 99, 37, 38
после сортировки: 75, 85, 99
удалить первый, который является 75
85, 99
удалить последний, который 99
'head' никогда не обновляется в' merge' или 'mergesort'. Вот почему вы все еще начинаете с того же узла после сортировки. – KompjoeFriek
@ KompjoeFriek Я не понимаю. Разве мой recmiddle не обновляет голову? –
№ 'findMiddle' ничего не обновляет. Также: я имел в виду «List.head», а не параметр функции (ей). – KompjoeFriek