Skip to main content

148. Sort List

分析

对归并排序并不熟悉,该题为归并排序的链表 + 迭代版本

能向上加入的 Option 有

  • 更改存储数据结构 (数组 -> 链表)
    • O(1)的空间复杂度在数组情况下达不到,链表可以
  • 更改调用模式 recursion -> iterative

摘录一段更改为 iterative 代码的核心

const mergeSort = (unsortedArray: number[]): number[] => {
// 不改变输入
unsortedArray = unsortedArray.slice()

// 核心部分
for (let size = 2; size < unsortedArray.length * 2; size *= 2) {
for (let start = 0; start < unsortedArray.length; start += size) {
const mid = Math.min(start + size / 2, unsortedArray.length)
const end = Math.min(start + size, unsortedArray.length)
merge(unsortedArray, start, mid, end)
}
}
return unsortedArray
}
sizestart 1start 2start 3start 4
20246
404812
8081624

size 理解为合并范围, size 的 最大值满足 size < unsortedArray.length * 2 来使得最大范围的时候可以包含整个数组的个数

题解

递归版本

/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/

function sortList(head: ListNode | null): ListNode | null {
if (!head?.next) {
return head
}
// 1 -> 2 -> 3 -> 4 -> 5
const middleNode = getMiddleNode(head)
const leftList = head
const rightList = middleNode.next
middleNode.next = null
// 1 -> 2 -> 3 4 -> 5
return merge(
sortList(leftList), sortList(rightList)
)
};

const merge = (head1: ListNode | null, head2: ListNode | null) => {
const dummyNode = new ListNode()
let p1 = head1, p2 = head2, p = dummyNode
while (p1 && p2) {
if (p1.val < p2.val) {
p.next = p1
p = p.next
p1 = p1.next
continue
}
p.next = p2
p = p.next
p2 = p2.next
}
p.next = p1 ? p1 : p2

return dummyNode.next
}


// 1 2 3 -> 2
// 1 2 3 4 -> 2
const getMiddleNode = (head: ListNode | null) => {
if (!head) {
return null
}
const dummyNode = new ListNode()
dummyNode.next = head
let slow = dummyNode, fast = dummyNode
while (fast?.next) {
fast = fast.next.next
slow = slow.next
}
return slow
}