148. 排序链表 (opens new window)

Description

Difficulty: 中等

Related Topics: 链表 (opens new window), 双指针 (opens new window), 分治 (opens new window), 排序 (opens new window), 归并排序 (opens new window)

给你链表的头结点 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⁴] 内
• -10⁵ <= Node.val <= 10⁵

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

Solution

Language: JavaScript

/**
 * 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}
 */
var sortList = function(head) {
 // 终止条件
 if (head == null || head.next == null) {
  return head
 }
 // 获取链表中间节点
 let midNode = getMiddleNode(head)
 let rightHead = midNode.next
 // 断开链表
 midNode.next = null

 let left = sortList(head)
 let right = sortList(rightHead)
 // 合并有序链表
 return mergeTwoLists(left, right)
};

// 利用快慢指针找到中间节点
var getMiddleNode = function (head) {
 if (head == null || head.next == null) {
  return head
 }
 let slow = head
 let fast = head.next.next
 while (fast != null && fast.next != null) {
  slow = slow.next
  fast = fast.next.next
 }
 return slow
}

// 合并两个有序链表
var mergeTwoLists = function (l1, l2) {
 let dmy = { next: null }
 let curr = dmy
 while (l1 != null && l2 != null) {
  if (l1.val < l2.val) {
   // [curr.next, l1] = [l1, l1.next]
   curr.next = l1
   l1 = l1.next
  } else {
   // [curr.next, l2] = [l2, l2.next]
   curr.next = l2
   l2 = l2.next
  }
  curr = curr.next
 }
 curr.next = l1 != null ? l1 : l2
 return dmy.next
}