Sort List

描述

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

分析

常数空间且O(nlogn)，单链表适合用归并排序，双向链表适合用快速排序。本题可以复用 Merge Two Sorted Lists 的代码。

代码

  1. // Sort List
  2. // 归并排序，时间复杂度O(nlogn)，空间复杂度O(1)
  3. public class Solution {
  4.     public ListNode sortList(ListNode head) {
  5.         if (head == null || head.next == null)return head;
  7.         final ListNode middle = findMiddle(head);
  8.         final ListNode head2 = middle.next;
  9.         middle.next = null; // 断开
  11.         final ListNode l1 = sortList(head);  // 前半段排序
  12.         final ListNode l2 = sortList(head2);  // 后半段排序
  13.         return mergeTwoLists(l1, l2);
  14.     }
  16.     // Merge Two Sorted Lists
  17.     private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  18.         ListNode dummy = new ListNode(-1);
  19.         for (ListNode p = dummy; l1 != null || l2 != null; p = p.next) {
  20.             int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
  21.             int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;
  22.             if (val1 <= val2) {
  23.                 p.next = l1;
  24.                 l1 = l1.next;
  25.             } else {
  26.                 p.next = l2;
  27.                 l2 = l2.next;
  28.             }
  29.         }
  30.         return dummy.next;
  31.     }
  32.     // 快慢指针找到中间节点
  33.     private static ListNode findMiddle(ListNode head) {
  34.         if (head == null) return null;
  36.         ListNode slow = head;
  37.         ListNode fast = head.next;
  39.         while (fast != null && fast.next != null) {
  40.             slow = slow.next;
  41.             fast = fast.next.next;
  42.         }
  43.         return slow;
  44.     }
  45. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/sorting/merge-sort/sort-list.html