排序链表

[louzhedong]

习题

出处 LeetCode 算法第148题

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

排序算法有很多种，此题要求时间复杂度在 O(n log n)，而且是链表的排序，所以采用归并排序是比较合适的。具体思路为：找到链表的中间节点，将左右两边的链表各自进行排序，最后进行归并，将两个排好序的链表合并为一个单独的链表（左右链表各自进行递归的排序操作）

解答

var sortList = function (head) {
  if (!head || !head.next) {
    return head;
  }

  var start = head;
  var count = 0;
  while (start) {
    count++;
    start = start.next;
  }
  var middle = Math.floor(count / 2);

  var prev = head;
  var current = head.next;
  for (var i = 0; i < middle - 1; i++) {
    prev = prev.next;
    current = current.next;
  }

  var left = head;
  prev.next = null;
  var right = current;

  left = sortList(left);
  right = sortList(right)
  var result = merge(left, right);
  return result;
};


function merge(left, right) {
  var temp = new ListNode();
  var _start = temp;
  while (left && right) {
    if (left.val <= right.val) {
      temp.next = left;
      left = left.next;
    } else {
      temp.next = right;
      right = right.next;
    }
    temp = temp.next;
  }

  if (left) {
    temp.next = left;
  }
  if (right) {
    temp.next = right
  }

  return _start.next;
}