Skip to main content

排序链表

题目​

给你链表的头结点 head, 请将其按升序排列并返回排序后的链表. 要求在 O(nlogn) 时间复杂度和常数级空间复杂度下解决.

示例

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

输出: [-1, 0, 3, 4, 5]

题解​

若要对链表达到 O(nlogn) 时间复杂度的排序, 需要使用 归并排序. 归并排序是分和治的过程, 因此可以使用 876. 链表的中间结点 来找到中点进行分, 通过 21. 合并两个有序链表 进行治.

下面这种方式使用了递归(自顶而下的归并排序), 会导致空间复杂度为 O(logn).

/**
 * 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) {
  // 如果没有 head, 或者 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 断开链表
  // 使得 head 为链表前半部分, mid 为链表后半部分
  slow.next = null

  return merge(sortList(head), sortList(mid))
}

// 21 题, 不多说
var merge = function (head1, head2) {
  const dummy = new ListNode(-1)
  let head = dummy
  let l1 = head1
  let l2 = head2

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

    head = head.next
  }

  if (l1) head.next = l1
  if (l2) head.next = l2

  return dummy.next
}
  • 时间复杂度: O(nlogn), 其中 n 是链表的长度
  • 空间复杂度: O(logn)