題目描述：給你鏈表的頭結(jié)點(diǎn) head 韭畸，請(qǐng)將其按 升序 排列并返回 排序后的鏈表 。
進(jìn)階：你可以在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下备禀，對(duì)鏈表進(jìn)行排序嗎趁仙？
示例：
例1：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
例2：
輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
例3：
輸入：head = []
輸出：[]
提示：
- 鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 5 * 104] 內(nèi)
- -10^5 <= Node.val <= 10^5
以下解題思路均來(lái)自于LeetCode官方題解
題解一：自頂向下歸并排序
解題思路：找到鏈表的中點(diǎn)，以中點(diǎn)為分界焚鲜，將鏈表拆分成兩個(gè)子鏈表掌唾。尋找鏈表的中點(diǎn)可以使用快慢指針的做法，快指針每次移動(dòng) 2 步忿磅，慢指針每次移動(dòng) 1 步糯彬，當(dāng)快指針到達(dá)鏈表末尾時(shí)，慢指針指向的鏈表節(jié)點(diǎn)即為鏈表的中點(diǎn)葱她。對(duì)兩個(gè)子鏈表分別排序撩扒。將兩個(gè)排序后的子鏈表合并，得到完整的排序后的鏈表吨些〈曜唬可以使用「21. 合并兩個(gè)有序鏈表」的做法炒辉，將兩個(gè)有序的子鏈表進(jìn)行合并。上述過(guò)程可以通過(guò)遞歸實(shí)現(xiàn)挽拔。遞歸的終止條件是鏈表的節(jié)點(diǎn)個(gè)數(shù)小于或等于 1辆脸，即當(dāng)鏈表為空或者鏈表只包含 1 個(gè)節(jié)點(diǎn)時(shí)，不需要對(duì)鏈表進(jìn)行拆分和排序螃诅。
解題語(yǔ)言：Swift
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func sortList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var fast = head, slow = head, temp = slow
while (fast != nil) {
temp = slow
slow = slow?.next
fast = fast!.next
if fast != nil {
fast = fast!.next
}
}
temp?.next = nil
let leftNode = sortList(head)
let rightNode = sortList(slow)
return merge(leftNode, rightNode)
}
func merge(_ first: ListNode?, _ second: ListNode?) -> ListNode? {
let newNode = ListNode(-1)
var temp = newNode
var newFirst = first, newSecond = second
while (newFirst != nil && newSecond != nil) {
if (newFirst!.val <= newSecond!.val) {
temp.next = newFirst
newFirst = newFirst!.next
} else {
temp.next = newSecond
newSecond = newSecond!.next
}
temp = temp.next!
}
if (newFirst != nil) {
temp.next = newFirst
}
1
if (newSecond != nil) {
temp.next = newSecond
}
return newNode.next
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(nlogn)啡氢，其中 n 是鏈表的長(zhǎng)度。
- 空間復(fù)雜度：O(logn)术裸，其中 n 是鏈表的長(zhǎng)度倘是。空間復(fù)雜度主要取決于遞歸調(diào)用的椣眨空間搀崭。
題解二：自底向上歸并排序
解題思路：使用自底向上的方法實(shí)現(xiàn)歸并排序，則可以達(dá)到 O(1)的空間復(fù)雜度猾编。首先求得鏈表的長(zhǎng)度 length瘤睹，然后將鏈表拆分成子鏈表進(jìn)行合并。具體做法如下答倡。
- 1.用 subLength 表示每次需要排序的子鏈表的長(zhǎng)度轰传，初始時(shí) subLength=1
- 2.每次將鏈表拆分成若干個(gè)長(zhǎng)度為 subLength 的子鏈表（最后一個(gè)子鏈表的長(zhǎng)度可以小于 subLength），按照每?jī)蓚€(gè)子鏈表一組進(jìn)行合并瘪撇，合并后即可得到若干個(gè)長(zhǎng)度為 subLength×2的有序子鏈表（最后一個(gè)子鏈表的長(zhǎng)度可以小于 subLength×2）获茬。合并兩個(gè)子鏈表仍然使用「21. 合并兩個(gè)有序鏈表」的做法。
- 3.將 subLength 的值加倍倔既，重復(fù)第 2 步恕曲，對(duì)更長(zhǎng)的有序子鏈表進(jìn)行合并操作，直到有序子鏈表的長(zhǎng)度大于或等于 length渤涌，整個(gè)鏈表排序完畢佩谣。
如何保證每次合并之后得到的子鏈表都是有序的呢？可以通過(guò)數(shù)學(xué)歸納法證明实蓬。
- 1.初始時(shí) subLength=1茸俭，每個(gè)長(zhǎng)度為 1 的子鏈表都是有序的。
- 2.如果每個(gè)長(zhǎng)度為 subLength 的子鏈表已經(jīng)有序瞳秽，合并兩個(gè)長(zhǎng)度為 subLength 的有序子鏈表瓣履，得到長(zhǎng)度為 subLength×2 的子鏈表，一定也是有序的练俐。
- 3.當(dāng)最后一個(gè)子鏈表的長(zhǎng)度小于 subLength 時(shí)袖迎，該子鏈表也是有序的，合并兩個(gè)有序子鏈表之后得到的子鏈表一定也是有序的。
因此可以保證最后得到的鏈表是有序的燕锥。
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func sortList(_ head: ListNode?) -> ListNode? {
if (head == nil) {
return head
}
var length = 0
var node = head
while (node != nil) {
length += 1
node = node?.next
}
let dummyHead = ListNode(0, head)
var subLength = 1
while subLength < length {
var prev = dummyHead, curr = dummyHead.next
while curr != nil {
let head1 = curr
var i = 1
while (i < subLength && curr != nil) {
curr = curr?.next
i += 1
}
let head2 = curr?.next
curr?.next = nil
curr = head2
var j = 1
while (j < subLength && curr != nil && curr?.next != nil) {
curr = curr?.next
j += 1
}
var next: ListNode?
if curr != nil {
next = curr?.next
curr?.next = nil
}
let merged = merge(head1, head2)
prev.next = merged
while prev.next != nil {
prev = prev.next!
}
curr = next
}
subLength *= 2
}
return dummyHead.next
}
func merge(_ first: ListNode?, _ second: ListNode?) -> ListNode? {
let newNode = ListNode(-1)
var temp = newNode
var newFirst = first, newSecond = second
while (newFirst != nil && newSecond != nil) {
if (newFirst!.val <= newSecond!.val) {
temp.next = newFirst
newFirst = newFirst!.next
} else {
temp.next = newSecond
newSecond = newSecond!.next
}
temp = temp.next!
}
if (newFirst != nil) {
temp.next = newFirst
}
1
if (newSecond != nil) {
temp.next = newSecond
}
return newNode.next
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(nlogn)辜贵，其中 n 是鏈表的長(zhǎng)度。
- 空間復(fù)雜度：O(1)归形。
