合并两个有序链表

题目描述：

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

进阶：

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

链接：

148. 排序链表 - 力扣（LeetCode） (leetcode-cn.com)

解题思路

思路一：归并排序（递归法）

要求时间空间复杂度分别为O(nlogn)和O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序

1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点（可以参考LeedCode 876：链表的中间结点）可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

2. 对两个子链表分别排序。

3. 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

// 合并有序链表
var merge = function (head1, head2) {
  var dummy = new ListNode();
  var curr = dummy,
    h1 = head1,
    h2 = head2;
  while (h1 !== null && h2 !== null) {
    if (h1.val <= h2.val) {
      curr.next = h1;
      h1 = h1.next;
    } else {
      curr.next = h2;
      h2 = h2.next;
    }
    curr = curr.next;
  }
  // if (h1 !== null) {
  //   curr.next = h1;
  // }
  // if (h2 !== null) {
  //   curr.next = h2;
  // }
  // 有未合并完的，直接将链表末尾指向未合并完的链表即可
  curr.next = h1 !== null ? h1 : h2;
  return dummy.next;
};
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  if (head === null || head.next === null) {
    return head;
  }
  var slow = head,
    fast = head.next;
  // 使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  var mid = slow.next;
  // 将链表切断
  slow.next = null;
  return merge(sortList(head), sortList(mid));
};

时间复杂度： O(nlogn)

空间复杂度： O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间

LeedCode 148：排序链表

合并两个有序链表

题目描述：

解题思路

思路一：归并排序（递归法）