题目

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

Example 1:

  1. Input: 4->2->1->3
  2. Output: 1->2->3->4

Example 2:

  1. Input: -1->5->3->4->0
  2. Output: -1->0->3->4->5

题意

将链表排序，要求不能使用额外空间，且时间复杂度为$O(NlogN)$。

思路

链表不好操作快排和堆排，使用归并排序(分治法)：每次利用快慢指针找到链表的中间位置，将其断开为左右两个子链表，待这两个子链表排序后，利用归并将它们再重新合并为一个有序链表。递归处理。

代码实现

Java

  1. class Solution {
  2.     public ListNode sortList(ListNode head) {
  3.         if (head == null || head.next == null) {
  4.             return head;
  5.         }
  7.         ListNode slow = head, fast = head;
  8.         while (fast.next != null && fast.next.next != null) {
  9.             slow = slow.next;
  10.             fast = fast.next.next;
  11.         }
  12.         ListNode mid = slow.next;
  13.         slow.next = null;
  14.         return merge(sortList(head), sortList(mid));
  15.     }
  17.     private ListNode merge(ListNode head1, ListNode head2) {
  18.         ListNode head = new ListNode(0);
  19.         ListNode cur = head;
  20.         while (head1 != null && head2 != null) {
  21.             if (head1.val < head2.val) {
  22.                 cur.next = head1;
  23.                 head1 = head1.next;
  24.             } else {
  25.                 cur.next = head2;
  26.                 head2 = head2.next;
  27.             }
  28.             cur = cur.next;
  29.         }
  30.         cur.next = head1 == null ? head2 : head1;
  31.         return head.next;
  32.     }
  33. }

JavaScript

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var sortList = function (head) {
  13.   if (!head || !head.next) {
  14.     return head
  15.   }
  17.   let slow = head, fast = head
  18.   while (fast.next && fast.next.next) {
  19.     fast = fast.next.next
  20.     slow = slow.next
  21.   }
  23.   let left = head, right = slow.next
  24.   slow.next = null
  25.   left = sortList(left)
  26.   right = sortList(right)
  28.   let dummy = new ListNode()
  29.   let p = dummy
  30.   while (left && right) {
  31.     let node = left.val <= right.val ? left : right
  32.     let tmp = node.next
  33.     node.next = null
  34.     p.next = node
  35.     p = p.next
  36.     node === left ? (left = tmp) : (right = tmp)
  37.   }
  38.   p.next = !left ? right : left
  40.   return dummy.next
  41. }