排序链表

[xszi]

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

示例 1:

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

示例 2:

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

leetcode

[xszi]

递归实现

let sortList = function(head) {
    return mergeSortRec(head)
}

// 归并排序
// 若分裂后的两个链表长度不为 1，则继续分裂
// 直到分裂后的链表长度都为 1，
// 然后合并小链表
let mergeSortRec = function (head) {
    if(!head || !head.next) {
        return head
    }

    // 获取中间节点
    let middle = middleNode(head)
    // 分裂成两个链表
    let temp = middle.next
    middle.next = null
    let left = head, right = temp
    // 继续分裂（递归分裂）
    left = mergeSortRec(left)
    right = mergeSortRec(right)
    // 合并两个有序链表
    return mergeTwoLists(left, right)
}

// 获取中间节点
// - 如果链表长度为奇数，则返回中间节点
// - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
let middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {
    let preHead = new ListNode(-1);
    let cur = preHead;
    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 || l2;
    return preHead.next;
}

引入递归算法的复杂度分析：

• 递归算法的时间复杂度：递归的总次数 * 每次递归的数量
• 递归算法的空间复杂度：递归的深度 * 每次递归创建变量的个数

复杂度分析

时间复杂度：递归的总次数为 T(logn) ，每次递归的数量为 T(n) ，时间复杂度为 O(nlogn)
空间复杂度：递归的深度为 T(logn) ，每次递归创建变量的个数为 T(c) （c为常数），空间复杂度为 O(logn)

迭代实现

var sortList = function (head) {
  const sentinelNode = new ListNode(0); // 哨兵结点
  sentinelNode.next = head;
  let len = 0, p = head;
  while (p) {
    p = p.next;
    len++;
  }

  for (let i = 1; i < len; i <<= 1) {
    let cur = sentinelNode.next, // 当前结点
      pre = sentinelNode; // 当前结点的前一个

    while (cur) {
      const left = cur;
      const right = cut(left, i); // 切割得到第二链表
      cur = cut(right, i); // 切割得到后面需要遍历的链表

      pre.next = merge(left, right); // 将得到的两个链表归并
      while (pre.next) {
        pre = pre.next;
      }
    }
  }

  return sentinelNode.next;
};

/* 切割并返回后面的链表 */
const cut = (head, n) => {
  let p = head;
  while (--n && p) {
    p = p.next;
  }
  if (!p) return null;

  const next = p.next;
  p.next = null;
  return next;
};

/* 将两个已经排序的链表归并 */
const merge = (l1, l2) => {
  const sentinelNode = new ListNode(0);
  let p = sentinelNode;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      p.next = l1;
      l1 = l1.next;
    } else {
      p.next = l2;
      l2 = l2.next;
    }
    p = p.next;
  }

  p.next = l1 ? l1 : l2; // 将其中一个有剩余结点的链表加在之后
  return sentinelNode.next;
};

复杂度分析

时间复杂度：时间复杂度为 O(n)
空间复杂度：空间复杂度为 O(1)