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)