148.排序链表

排序链表

给你链表的头结点 head，请将其按 升序 排列并返回排序后的链表。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, $5 * 10^4$] 内
• $-10^5$ <= Node.val <= $10^5$

解析

归并排序：用快慢指针找中点，分成两半后递归排序再合并。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  if (!head || !head.next) return head;

  // 快慢指针找中点
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const mid = slow.next;
  slow.next = null; // 断开

  const left = sortList(head);
  const right = sortList(mid);

  // 合并两个有序链表
  const dummy = new ListNode(0);
  let curr = dummy;
  let l = left,
    r = right;
  while (l && r) {
    if (l.val <= r.val) {
      curr.next = l;
      l = l.next;
    } else {
      curr.next = r;
      r = r.next;
    }
    curr = curr.next;
  }
  curr.next = l || r;
  return dummy.next;
};

链表归并排序的时间复杂度 O(nlogn)，空间复杂度 O(logn)（递归栈）。