单链表快速排序
点击(此处)折叠或打开
站在用户的角度思考问题，与客户深入沟通，找到安溪网站设计与安溪网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都做网站、网站设计、企业官网、英文网站、手机端网站、网站推广、域名申请、网站空间、企业邮箱。业务覆盖安溪地区。
-
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();
-
}
- }
148. Sort List
Sort a linked list in O(n log n) time using constant space complexity.
本文标题：单链表快速排序
URL网址：http://scjbc.cn/article/iiihdp.html
