排序链表
题目
给你链表的头结点 head, 请将其按升序排列并返回排 序后的链表. 要求在 O(nlogn)
时间复杂度和常数级空间复杂度下解决.
示例
输入: head = [-1, 5, 3, 4, 0]
输出: [-1, 0, 3, 4, 5]
题解
- JavaScript - 递归
- JavaScript - 迭代
若要对链表达到 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)
使用自底向上的方法实现归并排序, 可以达到 O(1)
的空间复杂度. 它的思路是先两个两个的 merge, 再四个四个的 merge... 直到结束. 举个例子 [4, 3, 1, 7, 8, 9, 2, 11, 5, 6]
:
step = 1: (3 -> 4) -> (1 -> 7) -> (8 -> 9) -> (2 -> 11) -> (5 -> 6)
step = 2: (1 -> 3 -> 4 -> 7) -> (2 -> 8 -> 9 -> 11) -> (5 -> 6)
step = 4: (1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> 11) -> (5 -> 6)
step = 8: (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 11)
具体直接看代码注释:
/**
* 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 || !head.next) return head
// 首先获取链表的长度
let length = 0
let node = head
while (node) {
length++
node = node.next
}
const dummy = new ListNode(-1, head)
// step <<= 1 等价于 step *= 2, 用于每两个一组, 每四个一组, 每八个一组...
for (let step = 1; step < length; step <<= 1) {
let curr = dummy.next
let tail = dummy
while (curr) {
// left -> @ -> @ -> @ -> @ -> @ -> @ -> @ -> null
let left = curr
// 将链表拆成两部分, 左边为 step 长度的链表, 右边为剩余链表
// left -> @ -> @ -> null
// right -> @ -> @ -> @ -> @ -> @ -> null
let right = cut(left, step)
// 把 right 继续切分, 使得 right 也为 step 长度的链表, curr 为剩余链表
// left -> @ -> @ -> null
// right -> @ -> @ -> null
// curr -> @ -> @ -> @ -> null
curr = cut(right, step)
// 将左右子链表 merge 后, 放到 tail 后面
tail.next = merge(left, right)
// 保证 tail 始终在链表的最后, 这是为了下一次拼接
while (tail.next) {
tail = tail.next
}
}
}
return dummy.next
}
// 在 step 位置断链, 并返回后面部分的链头
var cut = function (head, step) {
let node = head
while (--step && node) {
node = node.next
}
if (!node) return null
// 后半部分的链头
const next = node.next
// 断链操作, 将前半部分跟后半部分断开
node.next = null
// 返回后面部分的链头
return next
}
// 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(1)