快上网专注成都网站设计 成都网站制作 成都网站建设
成都网站建设公司服务热线:028-86922220

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

单链表快速排序

点击(此处)折叠或打开

站在用户的角度思考问题,与客户深入沟通,找到安溪网站设计与安溪网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、网站设计、企业官网、英文网站、手机端网站、网站推广、域名申请网站空间、企业邮箱。业务覆盖安溪地区。

  1. public class LinkedListSortTest {
  2.     //bubble up
  3.     public static ListNode sortList(ListNode head) {
  4.         ListNode m = head;
  5.         ListNode tail = null;
  6.         while (m != tail && m.next != null) {
  7.             ListNode n = head;
  8.             while (n.next != null) {
  9.                 if (n.next.val < n.val) {
  10.                     swap(n, n.next);
  11.                 }
  12.                 n = n.next;
  13.             }
  14.             tail = n;
  15.             m = m.next;
  16.         }
  17.         return head;
  18.     }
  19.     
  20.     //quick sort
  21.     public static ListNode sortList2(ListNode head) {
  22.         ListNode next = head.next;
  23.         if (next == null) { // 1 element
  24.             return head;
  25.         } else if (next.next == null) { // 2 elements
  26.             if (head.val > next.val) {
  27.                 swap(head, next);
  28.             }
  29.             return head;
  30.         } else {
  31.             ListNode mid = getMidNode(head);
  32.             return merge(sortList(head), sortList(mid));
  33.         }
  34.     }


  35.     private static ListNode merge(ListNode m, ListNode n) {
  36. //        System.out.println("Merge " + m + " with " + n);
  37.         
  38.         ListNode head = new ListNode(0);
  39.         ListNode tail = head;
  40.         while (m != null && n != null) {
  41.             if (m.val < n.val) {
  42.                 tail.next = m;
  43.                 m = m.next;
  44.             } else {
  45.                 tail.next = n;
  46.                 n = n.next;
  47.             }
  48.             tail = tail.next;
  49.         }
  50.         if (m != null) {
  51.             tail.next = m;
  52.         }
  53.         if (n != null) {
  54.             tail.next = n;
  55.         }
  56. //        System.out.println("Merge result : " + head.next);
  57.         return head.next;
  58.     }

  59.     private static ListNode getMidNode(ListNode n) {
  60.         ListNode fast = n;
  61.         ListNode slow = n;
  62.         while (true){
  63.             if (fast.next != null) {
  64.                 fast = fast.next;
  65.                 if (fast.next != null) {
  66.                     fast = fast.next;
  67.                     slow = slow.next;
  68.                     continue;
  69.                 }
  70.             }
  71.             break;
  72.         }
  73.         ListNode mid = slow.next;
  74.         slow.next = null;
  75.         return mid;
  76.     }

  77.     private static void swap(ListNode n, ListNode m) {
  78.         int v = n.val;
  79.         n.val = m.val;
  80.         m.val = v;
  81.     }

  82.     public static void main(String[] args) {
  83.         ListNode head = new ListNode(0);
  84.         int i = 0;
  85.         ListNode n = head;
  86.         while (i++ < 20) {
  87.             n.next = new ListNode(i * 37 % 50);
  88. //            n.next = new ListNode(i);
  89.             n = n.next;
  90.         }

  91.         print(head);
  92.         print(sortList(head));
  93.         print(sortList2(head));

  94.     }

  95.     public static void print(ListNode n) {
  96.         while (n != null) {
  97.             System.out.print(n.val + " ");
  98.             n = n.next;
  99.         }
  100.         System.out.println();
  101.     }

  102. }

  103. class ListNode {
  104.     int val;
  105.     ListNode next;

  106.     ListNode(int x) {
  107.         val = x;
  108.     }
  109.     
  110.     public String toString() {
  111.         ListNode n = this;
  112.         StringBuilder sb = new StringBuilder("[");
  113.         while (n != null) {
  114.             sb.append(n.val + " ");
  115.             n = n.next;
  116.         }
  117.         sb.deleteCharAt(sb.length() - 1);
  118.         sb.append("]");
  119.         return sb.toString();
  120.     }
  121. }
来源于  https://leetcode.com/problems/sort-list/
148. Sort List 

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


名称栏目:单链表快速排序
网页链接:http://6mz.cn/article/iiihdp.html

其他资讯