Sort List

Sort a linked list in O(n logn) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

analyze

根据题意的要求, 锁定使用归并排序算法, 但是相对数组的归并排序, 有以下两个难点:

  • 问题一: 如何确认链表的中点?
  • 问题二: 链表如何 merge?

针对问题一, 可以使用快慢指针来确认链表的中点, 快指针每次走两步, 慢指针每次走一步, 慢指针最后的位置就是链表的中点位置, 步骤图解如下:

针对奇数情形:

slow
quick
dummy -> 1 -> null
slow quick
dummy -> 4 -> 2 -> 1 -> null
偶数:
slow quick
dummy -> 1 -> 2 -> null

针对偶数情形:

slow quick
dummy -> 1 -> 2 -> null

此外另外一个难点是如何进行 merge 操作。大体思路为

  1. 在 leftList 中找到比 rNode 小且最接近 rNode 的值 lNode;
  2. 将 rNode 插入 lNode 的后面;

步骤图解如下:

lNode rNode
dummy -> 1 -> 3 -> null 2 -> 4 -> null
lNode rNode
dummy -> 1 -> 2 -> 3 -> null 4 -> null
var sortList = function(head) {
const dummy = new ListNode(0)
dummy.next = head
let head0 = dummy.next
let slow = dummy, quick = dummy
while (quick.next) {
quick = quick.next
slow = slow.next
quick.next && (quick = quick.next)
}
// if the slow list is equal to the quick list, it means the current list only has one node.
if (slow === quick) return dummy.next
let rightList = slow.next
slow.next = null
let leftList = dummy
return merge(sortList(leftList.next), sortList(rightList))
}
var merge = function(leftList, rightList) {
const dummy = new ListNode(0)
dummy.next = leftList
let lNode = dummy
let rNode = rightList
while (lNode && rNode) {
while (lNode.next && lNode.next.val < rNode.val) {
lNode = lNode.next
}
let rNext = rNode.next
rNode.next = lNode.next
lNode.next = rNode
rNode = rNext
}
return dummy.next
}

姊妹题

147、143、234