点击(此处)折叠或打开

public class LinkedListSortTest {
//bubble up
public static ListNode sortList(ListNode head) {
ListNode m = head;
ListNode tail = null;
while (m != tail && m.next != null) {
ListNode n = head;
while (n.next != null) {
if (n.next.val < n.val) {
swap(n, n.next);
}
n = n.next;
}
tail = n;
m = m.next;
}
return head;
}
//quick sort
public static ListNode sortList2(ListNode head) {
ListNode next = head.next;
if (next == null) { // 1 element
return head;
} else if (next.next == null) { // 2 elements
if (head.val > next.val) {
swap(head, next);
}
return head;
} else {
ListNode mid = getMidNode(head);
return merge(sortList(head), sortList(mid));
}
}
private static ListNode merge(ListNode m, ListNode n) {
// System.out.println("Merge " + m + " with " + n);
ListNode head = new ListNode(0);
ListNode tail = head;
while (m != null && n != null) {
if (m.val < n.val) {
tail.next = m;
m = m.next;
} else {
tail.next = n;
n = n.next;
}
tail = tail.next;
}
if (m != null) {
tail.next = m;
}
if (n != null) {
tail.next = n;
}
// System.out.println("Merge result : " + head.next);
return head.next;
}
private static ListNode getMidNode(ListNode n) {
ListNode fast = n;
ListNode slow = n;
while (true){
if (fast.next != null) {
fast = fast.next;
if (fast.next != null) {
fast = fast.next;
slow = slow.next;
continue;
}
}
break;
}
ListNode mid = slow.next;
slow.next = null;
return mid;
}
private static void swap(ListNode n, ListNode m) {
int v = n.val;
n.val = m.val;
m.val = v;
}
public static void main(String[] args) {
ListNode head = new ListNode(0);
int i = 0;
ListNode n = head;
while (i++ < 20) {
n.next = new ListNode(i * 37 % 50);
// n.next = new ListNode(i);
n = n.next;
}
print(head);
print(sortList(head));
print(sortList2(head));
}
public static void print(ListNode n) {
while (n != null) {
System.out.print(n.val + " ");
n = n.next;
}
System.out.println();
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public String toString() {
ListNode n = this;
StringBuilder sb = new StringBuilder("[");
while (n != null) {
sb.append(n.val + " ");
n = n.next;
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
}

来源于 https://leetcode.com/problems/sort-list/
148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

ITPub博客

单链表快速排序

最新文章