leetcode 148 排序链表 (opens new window)

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

进阶：

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

示例 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 * 104] 内
• -105 <= Node.val <= 105

解答： 解题思路：归并排序 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

const toSortList = (head1, head2) => {
  let dummyHead = new ListNode(0);
  let temp = dummyHead, temp1 = head1, temp2 = head2;
  while(temp1 && temp2) {
    if(temp1.val <= temp2.val) {
      temp.next = temp1;
      temp1 = temp1.next;
    }else {
      temp.next = temp2;
      temp2 = temp2.next;
    }
    temp = temp.next;
  }
  if(temp1) { // 如果temp2已经走完，那么将temp.next接到temp2上
    temp.next = temp1;
  }
  if(temp2) { // 如果temp1已经走完，那么将temp.next接到temp2上
    temp.next = temp2;
  }
  return dummyHead.next;
}

const merge = (head, tail) => {
  if(head === null) return head;
  if(head.next === tail) {
    head.next = null;
    return head;
  }
  // 快慢指针求中心点
  let slow = head, fast = head;
  while(fast !== tail) {
    slow = slow.next;
    fast = fast.next;
    if(fast !== tail) {
      fast = fast.next;
    }
  }
  const mid = slow;
  return merge(toSortList(head, mid), toSortList(mid, tail));
}

var sortList = function(head) {
    return toSortList(head, null);
};