歡迎關(guān)注 leetcode 專欄
題目
對鏈表進(jìn)行插入排序。
插入排序的動(dòng)畫演示如上垮衷。從第一個(gè)元素開始冈闭，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）稼稿。
每次迭代時(shí)，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示）者吁，并原地將其插入到已排好序的鏈表中窘俺。
插入排序算法：
- 插入排序是迭代的，每次只移動(dòng)一個(gè)元素复凳，直到所有元素可以形成一個(gè)有序的輸出列表瘤泪。
- 每次迭代中灶泵，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢枚酝荆⑵洳迦搿?/li>
- 重復(fù)直到所有輸入數(shù)據(jù)插入完為止赦邻。
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
輸入的節(jié)點(diǎn)對象的定義
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
鏈接：https://leetcode-cn.com/problems/insertion-sort-list
解法
常規(guī)解法
思路：
- 考慮到鏈表的表頭可能常常會(huì)變化，不利于維護(hù)实檀，因此可創(chuàng)建一個(gè)永遠(yuǎn)不會(huì)被替換的表頭
ListNode(float('-inf'))惶洲，每次從該表頭開始比較 - 插入排序的子問題，就是將待排序的節(jié)點(diǎn)
current_node插入到已排序區(qū)膳犹，因此首先要在已排序區(qū)找到最后一個(gè)小于等于current_node值的節(jié)點(diǎn)cur恬吕，并將current_node插入到cur后面，以保持排序的穩(wěn)定性须床。 - 定義當(dāng)前已排序區(qū)的最后一個(gè)節(jié)點(diǎn)是
last铐料，如果cur是last，那么相當(dāng)于什么都不用動(dòng)侨颈，且current_node變成了新的last；如果不是芯义，則插入current_node到cur后面哈垢，并更新last的指針。
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head: return None
# 創(chuàng)建一個(gè)永遠(yuǎn)不會(huì)被替換的假頭
new_head = ListNode(float('-inf'))
new_head.next = head
last = head # 已排序區(qū)的最后一個(gè)節(jié)點(diǎn)扛拨，初始化為 head
while last.next:
# 待排序的節(jié)點(diǎn)
current_node = last.next
# 找到 current_node 的前一個(gè)節(jié)點(diǎn) cur耘分，小于等于是為了保持排序的穩(wěn)定
# 如果已排序區(qū)的值都 <= current_node ，則 cur 為 last
# 如果已排序區(qū)存在大于 current_node 的節(jié)點(diǎn)绑警，則 cur 會(huì)變成該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
cur = new_head
while cur != last and cur.next.val <= current_node.val:
cur = cur.next
# 插入 current_node 到正確位置
if cur == last:
# 更新已排序區(qū)的最后一個(gè)節(jié)點(diǎn)
last = current_node
else:
# 先把 current_node 從鏈表中分離出來
last.next = current_node.next
# 再插入 current_node 到 cur 與 cur.next 之間
current_node.next = cur.next
cur.next = current_node
return new_head.next
空間復(fù)雜度 O(1)求泰，只是額外申請了幾個(gè)變量的空間。
時(shí)間復(fù)雜度 O(N^2)：
- 最好情況下计盒，當(dāng)原來的鏈表是逆序時(shí)渴频，每次在已排序區(qū)只需要比較1次，總共只需要比較 N - 1 次北启，時(shí)間復(fù)雜度僅為 O(n)卜朗。
- 最差情況下，當(dāng)原來的鏈表是升序時(shí)咕村，對于第 i 個(gè)數(shù)场钉，需要比較 i - 1 次，總共需要比較 N*(N-1)/2 次懈涛，時(shí)間復(fù)雜度為 O(n^2)逛万。
- 當(dāng)鏈表是雜亂無章時(shí)，時(shí)間復(fù)雜度為 O(n^2)批钠。
數(shù)組解法
可以考慮先將鏈表轉(zhuǎn)化成數(shù)組宇植，然后對數(shù)組使用插入排序得封，再重新轉(zhuǎn)化為鏈表。
# 數(shù)組解法
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head: return None
# 將節(jié)點(diǎn)放入數(shù)組
nodes = []
node = head
while node:
nodes.append(node)
node = node.next
# 排序數(shù)組
# nodes = sorted(nodes, key=lambda x: x.val)
self.insertion_sort(nodes)
# 更新指針
for prev, cur in zip(nodes, nodes[1:]):
prev.next = cur
cur.next = None
return nodes[0]
def insertion_sort(self, arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key.val < arr[j].val :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
空間復(fù)雜度 O(N)当纱，創(chuàng)建了一個(gè)長度為 N 的數(shù)組呛每。
時(shí)間復(fù)雜度 O(N*logN)，分為三個(gè)部分：
- 遍歷一遍并插入到數(shù)組中坡氯，遍歷的時(shí)間復(fù)雜度為 O(N)
- 排序的復(fù)雜度晨横，如果用插入排序的話就是 O(N^2)
- 更新指針，復(fù)雜度也是 O(N)
如果把排序部分用歸并排序或快排來實(shí)現(xiàn)的話箫柳，總體的時(shí)間復(fù)雜度就可以降為 O(N*logN)手形。
執(zhí)行時(shí)間差這么多，有點(diǎn)奇怪悯恍，看了 leetcode 評論區(qū)库糠，有人說是測試集有問題，好吧~
更多刷題涮毫，盡在 leetcode 專欄
