標(biāo)題寫的“單列表”我猜大概率是“單鏈表”的筆誤。單鏈表singly linked list是數(shù)據(jù)結(jié)構(gòu)里最基礎(chǔ)也最容易被輕視的一節(jié)課。它不只是考試題后面的棧、隊(duì)列、哈希表的鏈地址法、圖的鄰接表、LRU緩存底層全是鏈表或者鏈表思想的變體。這篇文章就把單鏈表的創(chuàng)建和使用講透從節(jié)點(diǎn)的定義、頭插法和尾插法到查找、插入、刪除這些基本操作再把兩個(gè)高頻經(jīng)典問題——鏈表逆序和兩個(gè)升序鏈表合并——完整寫一遍。如果你正在做“單鏈表的基本操作實(shí)驗(yàn)”或者準(zhǔn)備面試刷鏈表題這篇可以直接照著敲代碼也能幫你避掉那些經(jīng)常讓人調(diào)一晚上的低級(jí)錯(cuò)誤。1. 為什么數(shù)組用得好好的還要搞出一個(gè)鏈表來1.1 數(shù)組的三處硬傷數(shù)組是大多數(shù)人學(xué)會(huì)的第一種數(shù)據(jù)結(jié)構(gòu)它確實(shí)好用連續(xù)內(nèi)存、按下標(biāo)直接訪問a[i]一步到位時(shí)間復(fù)雜度 O(1)。但數(shù)組的缺點(diǎn)在我實(shí)際寫程序時(shí)越來越明顯尤其在元素個(gè)數(shù)不確定、頻繁增刪的場(chǎng)景里。第一處硬傷是長(zhǎng)度固定。C 語言的數(shù)組聲明之后長(zhǎng)度就不能變必須提前估算最大值。估算大了浪費(fèi)內(nèi)存估算小了程序直接越界。Python 里的 list 雖然看著能隨便 append但底層是動(dòng)態(tài)數(shù)組擴(kuò)容時(shí)要申請(qǐng)一塊更大的內(nèi)存然后把舊數(shù)據(jù)全部搬過去這個(gè)搬遷成本是 O(n) 的。如果你往一個(gè)動(dòng)態(tài)數(shù)組里不斷頭插每次都要把已有元素一個(gè)個(gè)往后挪性能肉眼可見地拉胯。第二處硬傷是插入和刪除的代價(jià)太高。在數(shù)組中間插入一個(gè)元素需要把插入位置后面的所有元素依次后移一位刪除則是前移。假設(shè)數(shù)組長(zhǎng)度是 n在頭部插入就是 O(n)在中間隨機(jī)位置插入平均也是 O(n)。這在寫課程設(shè)計(jì)、做數(shù)據(jù)處理時(shí)很致命。第三處硬傷是內(nèi)存的連續(xù)性要求。數(shù)組必須占用一整塊連續(xù)的內(nèi)存空間。內(nèi)存被分來分去之后剩余的空閑塊可能都是零散的任何一個(gè)單獨(dú)的空閑塊都裝不下一個(gè)大數(shù)組。這時(shí)候系統(tǒng)要么觸發(fā)內(nèi)存整理要么分配失敗。1.2 鏈表的本質(zhì)用離散存儲(chǔ)換靈活操作鏈表的思路很簡(jiǎn)單既然連續(xù)的大塊內(nèi)存不好找那我就不找連續(xù)的了。每個(gè)元素放在一個(gè)獨(dú)立的“節(jié)點(diǎn)”里節(jié)點(diǎn)之間用指針串起來像一串珠子一樣。每個(gè)節(jié)點(diǎn)只干兩件事存自己的數(shù)據(jù)記下一個(gè)節(jié)點(diǎn)在哪兒。所以單鏈表的核心定義就是節(jié)點(diǎn)之間是線性邏輯關(guān)系但物理存儲(chǔ)是離散的。這個(gè)設(shè)計(jì)帶來幾個(gè)直接好處內(nèi)存分配靈活每個(gè)節(jié)點(diǎn)可以單獨(dú)分配不需要一次性申請(qǐng)一整塊。插入刪除只需要改指針不需要搬動(dòng)其他元素O(1) 完成。長(zhǎng)度天然動(dòng)態(tài)想加就加想刪就刪。代價(jià)也很明確不支持隨機(jī)訪問想找第 k 個(gè)節(jié)點(diǎn)必須從頭一個(gè)個(gè)往后走時(shí)間復(fù)雜度 O(n)每個(gè)節(jié)點(diǎn)多出一個(gè)指針域內(nèi)存占用比數(shù)組高另外由于節(jié)點(diǎn)在內(nèi)存里不連續(xù)CPU 緩存命中率低大數(shù)據(jù)量下遍歷性能不如數(shù)組。對(duì)比項(xiàng)數(shù)組單鏈表隨機(jī)訪問O(1)O(n)頭部插入O(n)O(1)頭部刪除O(n)O(1)內(nèi)存連續(xù)性要求連續(xù)不要求額外內(nèi)存開銷基本沒有每個(gè)節(jié)點(diǎn)一個(gè)指針域我見過不少同學(xué)一上來就糾結(jié)“哪個(gè)更好”。沒有更好只有合適。頻繁查找、數(shù)量穩(wěn)定用數(shù)組頻繁增刪、數(shù)量動(dòng)態(tài)用鏈表。這也是為什么實(shí)際項(xiàng)目里兩種都會(huì)用。1.3 指針也好引用也罷理解“節(jié)點(diǎn)”才是關(guān)鍵學(xué)鏈表的時(shí)候很多人被“指針”這個(gè)概念嚇住了。C 語言里指針就是一個(gè)變量存的是另一個(gè)變量的內(nèi)存地址。Python 里沒有指針這個(gè)說法但有個(gè)東西叫“引用”本質(zhì)是一樣的對(duì)象在內(nèi)存中有地址變量綁定到這個(gè)地址上。理解這一點(diǎn)特別重要。你在 Python 里寫a ListNode(1) b a b.val 2改的是同一個(gè)對(duì)象因?yàn)閍和b指向同一個(gè)內(nèi)存位置。鏈表的next字段存的就是下一個(gè)節(jié)點(diǎn)的引用或者指針。操作鏈表本質(zhì)上就是不斷問自己一個(gè)問題當(dāng)前這個(gè)節(jié)點(diǎn)的 next 應(yīng)該指向誰在紙上畫圖是理解鏈表的最好方式。一個(gè)節(jié)點(diǎn)畫成一個(gè)方塊左邊寫值右邊畫一個(gè)箭頭指向下一個(gè)方塊。所有指針操作跟著箭頭走一遍就通了。2. 從節(jié)點(diǎn)定義開始創(chuàng)建鏈表的兩種方法2.1 節(jié)點(diǎn)結(jié)構(gòu)怎么定義最順手無論用什么語言單鏈表的節(jié)點(diǎn)都長(zhǎng)一個(gè)樣一個(gè)數(shù)據(jù)域一個(gè)指針域/引用域。Python 版本用類定義class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC 語言版本用結(jié)構(gòu)體typedef struct Node { int data; struct Node *next; } Node;兩個(gè)版本一一對(duì)應(yīng)。val存數(shù)據(jù)next存下一個(gè)節(jié)點(diǎn)的位置。最后一個(gè)節(jié)點(diǎn)的next指向NonePython或者NULLC表示鏈表結(jié)束。這里有個(gè)細(xì)節(jié)節(jié)點(diǎn)定義里的nextNone是默認(rèn)參數(shù)。這樣創(chuàng)建單個(gè)節(jié)點(diǎn)時(shí)可以不傳 next寫node ListNode(5)它天然就是鏈表尾部。這個(gè)默認(rèn)值看起來不起眼實(shí)際寫代碼時(shí)能少寫很多判斷。2.2 尾插法順序不變最符合直覺的建鏈方式創(chuàng)建鏈表最直接的想法是新來的節(jié)點(diǎn)放到鏈表的最后面。這樣創(chuàng)建出來的鏈表順序和輸入順序完全一致。比如輸入[1, 2, 3]得到的鏈表就是1 - 2 - 3 - None。尾插法的實(shí)現(xiàn)需要維護(hù)一個(gè)尾指針每次都在尾指針后面掛新節(jié)點(diǎn)然后讓尾指針移動(dòng)到新節(jié)點(diǎn)上def create_by_tail(values): dummy ListNode() # 哨兵節(jié)點(diǎn)下面細(xì)說 tail dummy # 尾指針 for v in values: tail.next ListNode(v) # 新節(jié)點(diǎn)掛到尾部 tail tail.next # 尾指針后移 return dummy.next # 哨兵的下一個(gè)才是真正的頭節(jié)點(diǎn)你注意這里的dummy節(jié)點(diǎn)。它本身不存有效數(shù)據(jù)作用是讓代碼在鏈表為空時(shí)也能統(tǒng)一處理。沒有 dummy 的話往空鏈表里加第一個(gè)節(jié)點(diǎn)時(shí)要額外判斷if head is None代碼會(huì)丑很多。后面合并兩個(gè)鏈表時(shí)這種哨兵節(jié)點(diǎn)更是神器。2.3 頭插法代碼最簡(jiǎn)潔但鏈表是反的頭插法的思路反過來每次把新節(jié)點(diǎn)插到鏈表的頭部讓新節(jié)點(diǎn)成為新的頭節(jié)點(diǎn)。def create_by_head(values): head None for v in values: new_node ListNode(v) new_node.next head head new_node return head代碼非常短但有一個(gè)容易忽略的副作用輸入順序和鏈表順序相反。輸入[1, 2, 3]得到的是3 - 2 - 1 - None。為什么會(huì)反因?yàn)槊看涡鹿?jié)點(diǎn)都跑到最前面了后輸入的反而在鏈頭。這個(gè)特性不是 bug它可以被反過來利用如果你有一批逆序數(shù)據(jù)想得到正序鏈表或者實(shí)現(xiàn)“后進(jìn)先出”的棧結(jié)構(gòu)頭插法正好合適。很多教科書在講“棧的鏈表實(shí)現(xiàn)”時(shí)用的就是頭插法思路。2.4 哨兵節(jié)點(diǎn)到底要不要實(shí)戰(zhàn)中的選擇上一節(jié)代碼里出現(xiàn)了dummy很多初學(xué)者會(huì)困惑這不是白造了一個(gè)節(jié)點(diǎn)嗎哨兵節(jié)點(diǎn)的價(jià)值在于消除邊界條件的特殊處理。舉個(gè)例子刪除一個(gè)節(jié)點(diǎn)正常的邏輯是找到前驅(qū)節(jié)點(diǎn) prev然后prev.next prev.next.next。但如果要?jiǎng)h的是頭節(jié)點(diǎn)它沒有前驅(qū)就要單獨(dú)寫一個(gè)分支。有了哨兵節(jié)點(diǎn)之后頭節(jié)點(diǎn)也變成了“某個(gè)節(jié)點(diǎn)的下一個(gè)”所有刪除操作統(tǒng)一成同一種寫法。建鏈方式是否需要哨兵結(jié)果順序適用場(chǎng)景尾插法推薦和輸入一致一般業(yè)務(wù)數(shù)據(jù)、完整創(chuàng)建頭插法不需要和輸入相反棧結(jié)構(gòu)、逆序構(gòu)建我的個(gè)人建議是刷題和寫項(xiàng)目時(shí)都用哨兵節(jié)點(diǎn)養(yǎng)成習(xí)慣。它讓你少想很多 if 分支代碼也更不容易出 bug。唯一的代價(jià)就是多一個(gè)節(jié)點(diǎn)的內(nèi)存現(xiàn)代計(jì)算機(jī)完全不在乎這一點(diǎn)。3. 基本操作實(shí)驗(yàn)遍歷、查找、插入、刪除3.1 遍歷和求長(zhǎng)度所有操作的地基遍歷是最基礎(chǔ)的操作思路就是“從頭開始跟著 next 一直走走到 None 為止”def traverse(head): cur head while cur is not None: print(cur.val) cur cur.next求鏈表長(zhǎng)度的代碼幾乎一樣只是把打印換成計(jì)數(shù)def length(head): count 0 cur head while cur is not None: count 1 cur cur.next return count這里有一個(gè)新手很容易犯的錯(cuò)有人在 while 里寫了cur.next然后循環(huán)里又移動(dòng)cur。仔細(xì)看如果你寫的是while cur.next is not None那循環(huán)結(jié)束時(shí)停在了最后一個(gè)節(jié)點(diǎn)上最后一個(gè)節(jié)點(diǎn)的值就沒處理到。統(tǒng)一用while cur is not None判斷邏輯最簡(jiǎn)單。3.2 按值查找和按下標(biāo)訪問按值查找就是遍歷一遍比較每個(gè)節(jié)點(diǎn)的 valdef find_by_value(head, target): cur head pos 0 while cur is not None: if cur.val target: return pos cur cur.next pos 1 return -1 # 沒找到按下標(biāo)訪問也一樣只是判斷條件從“值相等”變成“走夠了步數(shù)”def get_by_index(head, index): cur head for _ in range(index): if cur is None: raise IndexError(下標(biāo)越界) cur cur.next if cur is None: raise IndexError(下標(biāo)越界) return cur.val注意越界判斷。鏈表不支持隨機(jī)訪問按下標(biāo)訪問是 O(n)這是鏈表的固有特性。如果頻繁按位置訪問說明你選錯(cuò)了數(shù)據(jù)結(jié)構(gòu)。3.3 插入操作先連后繼再連前驅(qū)在鏈表第 pos 個(gè)位置后面插入一個(gè)新節(jié)點(diǎn)核心操作兩步def insert_after(prev_node, new_node): 在 prev_node 后面插入 new_node new_node.next prev_node.next prev_node.next new_node這兩行的順序不能反。我當(dāng)年第一次寫的時(shí)候就是反著來的# 錯(cuò)誤示范 prev_node.next new_node # 先把 prev 指向新節(jié)點(diǎn) new_node.next prev_node.next # 但 prev_node.next 已經(jīng)變成 new_node 自己了反了之后新節(jié)點(diǎn) next 指向了自己形成自環(huán)鏈表從那里斷成兩截后面所有節(jié)點(diǎn)徹底丟失。正確的邏輯永遠(yuǎn)是先把新節(jié)點(diǎn)的后繼接到原后繼上再把前驅(qū)的 next 接到新節(jié)點(diǎn)上。注意這個(gè)順序插到頭節(jié)點(diǎn)、插到中間、插到末尾都一樣。類比一下你想在一列隊(duì)伍里插隊(duì)一定是你先拉住后面那個(gè)人的手再讓前面那個(gè)人拉住你。如果前面那個(gè)人先松手拉住你后面那個(gè)人就找不到了。3.4 刪除節(jié)點(diǎn)找到前驅(qū)是關(guān)鍵刪除的本質(zhì)是讓目標(biāo)節(jié)點(diǎn)的前驅(qū)直接跳過目標(biāo)節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的后繼。def delete_node(head, target_val): dummy ListNode(0) dummy.next head prev dummy cur head while cur is not None: if cur.val target_val: prev.next cur.next return dummy.next prev cur cur cur.next return dummy.next幾個(gè)要點(diǎn)借助 dummy 以后刪除頭節(jié)點(diǎn)也只是普通情況不需要單獨(dú)寫 if。刪除操作真正的難度不是“刪”這一步而是“找到前驅(qū)”。單鏈表只能往后走你不能從當(dāng)前節(jié)點(diǎn)回頭找它的前驅(qū)所以必須用一個(gè) prev 指針跟在后面。C 語言里刪除節(jié)點(diǎn)還要手動(dòng)free(cur)否則會(huì)內(nèi)存泄漏Python 有垃圾回收不需要這一步但你要明白在這個(gè)語言里節(jié)點(diǎn)是何時(shí)被回收的。3.5 一個(gè)完整可運(yùn)行的鏈表類“基本操作實(shí)驗(yàn)”直接抄把上面的操作組裝成一個(gè)類就是課程里常見的“單鏈表基本操作實(shí)驗(yàn)”class SinglyLinkedList: def __init__(self): self.head None self.size 0 def insert_head(self, val): 頭插法插入 node ListNode(val) node.next self.head self.head node self.size 1 def append(self, val): 尾插法插入 node ListNode(val) if self.head is None: self.head node else: cur self.head while cur.next is not None: cur cur.next cur.next node self.size 1 def insert(self, index, val): 在下標(biāo) index 處插入 if index 0 or index self.size: raise IndexError(下標(biāo)越界) if index 0: self.insert_head(val) return prev self.head for _ in range(index - 1): prev prev.next node ListNode(val) node.next prev.next prev.next node self.size 1 def delete(self, index): 刪除下標(biāo) index 處的節(jié)點(diǎn) if index 0 or index self.size: raise IndexError(下標(biāo)越界) if index 0: self.head self.head.next else: prev self.head for _ in range(index - 1): prev prev.next prev.next prev.next.next self.size - 1 def find(self, val): 按值查找返回下標(biāo) cur self.head pos 0 while cur is not None: if cur.val val: return pos cur cur.next pos 1 return -1 def display(self): cur self.head values [] while cur is not None: values.append(str(cur.val)) cur cur.next print( - .join(values) - None)這個(gè)類能覆蓋絕大多數(shù)課程實(shí)驗(yàn)和面試基礎(chǔ)題的測(cè)試需求。注意size字段的維護(hù)插入時(shí)加一刪除時(shí)減一。很多人漏掉這一步后面查找和插入的下標(biāo)判斷就會(huì)出 bug。調(diào)試鏈表的題建議先把“遍歷打印”寫出來每操作一步就打印一次鏈表比盯代碼快得多。4. 單鏈表逆序最容易丟指針的經(jīng)典題4.1 迭代反轉(zhuǎn)三個(gè)指針的接力“python 單鏈表逆序”是熱搜經(jīng)常出現(xiàn)的題面試?yán)镆矌缀醣乜?。它的要求是不新建鏈表只改指針方向把鏈表整個(gè)反過來。迭代法的核心思路是三個(gè)指針prev記錄當(dāng)前節(jié)點(diǎn)的前驅(qū)cur記錄當(dāng)前節(jié)點(diǎn)nxt記錄當(dāng)前節(jié)點(diǎn)的后繼。每到一個(gè)節(jié)點(diǎn)先把后繼存下來再把當(dāng)前節(jié)點(diǎn)的 next 指向 prev然后三個(gè)指針整體前移def reverse_list(head): prev None cur head while cur is not None: nxt cur.next # 先保存后繼 cur.next prev # 指針反轉(zhuǎn) prev cur # prev 前移 cur nxt # cur 前移 return prev # 新的頭節(jié)點(diǎn)很多初學(xué)者在循環(huán)里不知道第三步該干什么硬生生把cur cur.next寫進(jìn)去。問題在于cur.next已經(jīng)在第二步被改成了prev你再cur cur.next就回到了原來的前驅(qū)永遠(yuǎn)在原地打轉(zhuǎn)。所以必須提前用nxt保存好原來的后繼。代碼返回的是prev而不是cur因?yàn)檠h(huán)結(jié)束時(shí)cur已經(jīng)變成Noneprev停在原鏈表的尾節(jié)點(diǎn)上。尾節(jié)點(diǎn)反轉(zhuǎn)后變成了頭節(jié)點(diǎn)它就是新鏈表的頭。建議畫圖走一遍輸入1 - 2 - 3 - None手動(dòng)模擬指針變化。我在給學(xué)生講這塊時(shí)發(fā)現(xiàn)只要能在紙上完整畫出每一輪三個(gè)指針的位置迭代反轉(zhuǎn)就算真正學(xué)會(huì)了。4.2 遞歸反轉(zhuǎn)函數(shù)棧幫你完成一半工作遞歸法代碼更短但對(duì)初學(xué)者來說更難理解def reverse_recursive(head): if head is None or head.next is None: return head new_head reverse_recursive(head.next) head.next.next head head.next None return new_head理解遞歸反轉(zhuǎn)有兩個(gè)關(guān)鍵點(diǎn)。第一遞歸函數(shù)返回的是“反轉(zhuǎn)后的新頭節(jié)點(diǎn)”。假設(shè)鏈表是1 - 2 - 3 - None調(diào)用reverse_recursive(1)時(shí)它先調(diào)用reverse_recursive(2)后者又調(diào)用reverse_recursive(3)。最深層遞歸到節(jié)點(diǎn) 3 時(shí)3.next是 None直接返回 3此時(shí)3就是整條鏈表反轉(zhuǎn)后的頭。第二回溯時(shí)只看兩層。從節(jié)點(diǎn) 3 回到節(jié)點(diǎn) 2 那一層時(shí)head是 2head.next是 3。代碼做的事是2.next.next 2也就是讓 3 的 next 指向 2形成3 - 2然后把2.next置為 None防止出現(xiàn)循環(huán)。每一層都做同樣的操作最后整條鏈就反過來了。4.3 逆序操作里最容易踩的三個(gè)坑這個(gè)題幾乎每個(gè)新手都會(huì)踩坑我總結(jié)三個(gè)最常見的坑一返回錯(cuò)了節(jié)點(diǎn)。迭代法最后返回prev遞歸法返回new_head。有人寫迭代時(shí)圖省事返回cur但此時(shí)cur是 None等于返回了一個(gè)空鏈表打印出來什么都沒有?？佣f歸深度過大。Python 默認(rèn)遞歸深度限制在 1000 左右鏈表長(zhǎng)度超過這個(gè)數(shù)就會(huì)拋RecursionError。面試時(shí)用遞歸寫法沒問題但如果你在真實(shí)項(xiàng)目里反轉(zhuǎn)一個(gè)上萬元素的鏈表老老實(shí)實(shí)用迭代。坑三忘了把原來的頭節(jié)點(diǎn) next 置空。反轉(zhuǎn)前頭節(jié)點(diǎn)變成了尾節(jié)點(diǎn)它的 next 必須指向 None。迭代法里因?yàn)閜rev初始是 None反轉(zhuǎn)后原頭節(jié)點(diǎn)的 next 自然變成 None沒問題。但遞歸法必須手動(dòng)寫head.next None否則鏈表末尾會(huì)成環(huán)遍歷時(shí)直接死循環(huán)。5. 已知兩個(gè)長(zhǎng)度為 m 和 n 的升序單鏈表合并操作的完整拆解5.1 合并升序鏈表的基本思路這個(gè)熱搜題給的背景是“已知兩個(gè)長(zhǎng)度為 m 和 n 的升序單鏈表”任務(wù)通常是合并成一個(gè)升序鏈表。這是面試?yán)镦湵眍}的?？鸵彩菤w并排序在鏈表上的基礎(chǔ)操作。核心思路一句話兩個(gè)鏈表同時(shí)從頭往后走誰的當(dāng)前節(jié)點(diǎn)值小誰就接到結(jié)果鏈表后面然后那個(gè)鏈表的指針往后走一步重復(fù)這個(gè)過程直到某個(gè)鏈表走完把另一個(gè)鏈表剩下的一整段接上。前提條件是兩個(gè)鏈表都已經(jīng)是升序的。如果其中一個(gè)為空合并結(jié)果就是另一個(gè)鏈表本身。5.2 迭代實(shí)現(xiàn)哨兵節(jié)點(diǎn)讓代碼變得優(yōu)雅def merge_two_sorted_lists(l1, l2): dummy ListNode() cur dummy while l1 is not None and l2 is not None: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next # 把剩余部分直接接上 cur.next l1 if l1 is not None else l2 return dummy.next這段代碼里的哨兵節(jié)點(diǎn)dummy發(fā)揮了巨大作用。沒有它你要費(fèi)心思判斷“結(jié)果鏈表的第一個(gè)節(jié)點(diǎn)到底是誰”有了它所有新節(jié)點(diǎn)一律掛在cur.next上最后dummy.next就是結(jié)果鏈表的頭。cur.next l1 if l1 is not None else l2這一行很巧妙。因?yàn)閮蓚€(gè)鏈表都是升序的剩下的部分也必然是升序的而且剩下來的所有節(jié)點(diǎn)一定比已經(jīng)接好的節(jié)點(diǎn)都大可以直接整段拼接。不需要再一個(gè)個(gè)遍歷。5.3 遞歸實(shí)現(xiàn)更短但不是所有場(chǎng)景都適合遞歸的思路更數(shù)學(xué)化比較兩個(gè)頭節(jié)點(diǎn)的大小小的那個(gè)作為結(jié)果頭節(jié)點(diǎn)它的 next 指向“剩余兩個(gè)鏈表合并后的結(jié)果”。def merge_two_sorted_lists_recursive(l1, l2): if l1 is None: return l2 if l2 is None: return l1 if l1.val l2.val: l1.next merge_two_sorted_lists_recursive(l1.next, l2) return l1 else: l2.next merge_two_sorted_lists_recursive(l1, l2.next) return l2遞歸方法和迭代方法的時(shí)間復(fù)雜度一樣都是 O(mn)因?yàn)槊總€(gè)節(jié)點(diǎn)都被比較了一次。但空間復(fù)雜度有區(qū)別迭代法只用常數(shù)個(gè)指針空間 O(1)遞歸法每一次調(diào)用都會(huì)占用函數(shù)?？臻g最壞情況遞歸深度達(dá)到 mn空間 O(mn)。所以大數(shù)據(jù)量或者面試要求 O(1) 空間時(shí)用迭代。5.4 合并后的變種問題理解了基本合并幾個(gè)變種也就順了合并 k 個(gè)升序鏈表可以用“兩兩合并”的方式也可以借助最小堆每次從 k 個(gè)頭節(jié)點(diǎn)中取最小值。時(shí)間復(fù)雜度是 O(N log k)N 是節(jié)點(diǎn)總數(shù)。兩個(gè)升序鏈表求交集/并集思路和合并幾乎一樣只是拼接條件變成“值相等才接”“值小時(shí)移動(dòng)指針”。合并后去除重復(fù)節(jié)點(diǎn)合并時(shí)如果發(fā)現(xiàn)cur.val和結(jié)果鏈表最后一個(gè)節(jié)點(diǎn)的 val 一樣就不接這個(gè)重復(fù)節(jié)點(diǎn)。面試時(shí)如果遇到這些變種題先在紙上寫出基本合并模板再改條件比硬背答案靠譜得多。6. 實(shí)操經(jīng)驗(yàn)?zāi)切┙?jīng)常讓人調(diào)一晚上的問題6.1 指針丟失鏈表世界里最貴的“手滑”指針丟失往往只有一個(gè)原因在連接新指針之前把舊指針提前覆蓋了。就像你搬家具先把舊柜子推倒再準(zhǔn)備搬新柜子結(jié)果舊柜子里的東西全散了。最常見的兩處插入時(shí)沒保存后繼。在中間插入節(jié)點(diǎn)如果先執(zhí)行prev.next new_node原來的prev.next指向的節(jié)點(diǎn)就找不到了后面整段鏈表全部丟失。正確做法是先new_node.next prev.next再prev.next new_node。反轉(zhuǎn)或換位時(shí)沒保存后繼。凡是“把某個(gè)節(jié)點(diǎn)的 next 指向別處”的操作都要先想清楚原來的 next 還有沒有人保存如果沒人保存先存到一個(gè)臨時(shí)變量里。判斷“會(huì)不會(huì)丟指針”我有個(gè)笨辦法每次寫完一個(gè)操作問自己一個(gè)連環(huán)問題——有沒有節(jié)點(diǎn)在操作后同時(shí)被兩個(gè)指針指向有沒有節(jié)點(diǎn)一個(gè)指針都不指向如果一個(gè)節(jié)點(diǎn)一個(gè)指針都不指向了要么它馬上被垃圾回收Python要么它就從鏈表里永久消失了。6.2 邊界條件空鏈表、單節(jié)點(diǎn)、頭節(jié)點(diǎn)和尾節(jié)點(diǎn)我在批改學(xué)生的實(shí)驗(yàn)報(bào)告時(shí)發(fā)現(xiàn)很多 bug 根本不是邏輯錯(cuò)而是邊界條件沒處理。鏈表題必須養(yǎng)成的肌肉記憶是每次寫完代碼立刻檢查四類情況鏈表為空head是 None遍歷循環(huán)一次都不執(zhí)行。鏈表中只有一個(gè)節(jié)點(diǎn)循環(huán)條件cur.next和cur的區(qū)別會(huì)在這里暴露。操作頭節(jié)點(diǎn)插入、刪除、反轉(zhuǎn)都需要單獨(dú)看頭節(jié)點(diǎn)邏輯是否成立。操作尾節(jié)點(diǎn)cur.next is None的處理比如在刪除時(shí)要把前驅(qū)的 next 置為 None而不能是野指針。一個(gè)偷懶的通用解法給鏈表加哨兵節(jié)點(diǎn)。有了dummy空表和頭節(jié)點(diǎn)特判基本都能消除。我刷題時(shí)幾乎每個(gè)關(guān)于刪除、插入、合并的題都會(huì)先定義一個(gè)dummy ListNode(0)省下大量腦力。6.3 Python 和 C 在鏈表操作上的差異很多教材用 C 語言講鏈表你照著寫成 Python 時(shí)會(huì)有幾個(gè)明顯差異照著下面這個(gè)表對(duì)照檢查就行操作C 語言Python節(jié)點(diǎn)定義struct typedefclass指向下一個(gè)指針變量對(duì)象引用空鏈表判斷head NULLhead is None刪除節(jié)點(diǎn)手動(dòng) free(node)自動(dòng)垃圾回收訪問字段node-nextnode.next指針運(yùn)算支持不支持Python 沒有指針運(yùn)算所以“鏈表的 next 指向誰”就體現(xiàn)在引用賦值上。另外 Python 里一切變量都是對(duì)象引用寫new_node old_node之后改任意一個(gè)的 next另一個(gè)也會(huì)跟著變除非你顯式創(chuàng)建一個(gè)新節(jié)點(diǎn)。這個(gè)特性在 C 里不容易搞混Python 里容易踩。6.4 調(diào)試鏈表的幾種實(shí)用手段鏈表出 bug 時(shí)不要用眼睛硬摳代碼。我通常按這個(gè)順序來先打印。在每次循環(huán)末尾打印當(dāng)前鏈表所有節(jié)點(diǎn)的值看哪一步開始不對(duì)。這個(gè)方法最土但最有效。為了打印方便提前寫好display函數(shù)平時(shí)無所謂調(diào)試時(shí)它就是你的命根子。再畫圖。在紙上把幾個(gè)關(guān)鍵節(jié)點(diǎn)畫成方塊上面寫數(shù)據(jù)下面寫 next 指向手動(dòng)模擬代碼一行行執(zhí)行。特別是反轉(zhuǎn)、插入、刪除這類改指針的操作畫一遍基本就能定位問題。最后寫測(cè)試用例。不要只測(cè)正常鏈表把空鏈表、單節(jié)點(diǎn)鏈表、兩個(gè)節(jié)點(diǎn)鏈表、目標(biāo)在頭節(jié)點(diǎn)、目標(biāo)在尾節(jié)點(diǎn)這五類情況都測(cè)一遍。很多邊界 bug 都是這樣測(cè)出來的。鏈表的問題幾乎都是“畫一畫就通了”的問題。很多人覺得鏈表難其實(shí)是卡在“不動(dòng)筆只動(dòng)腦”。你如果真的拿紙筆把指針的變化從頭到尾畫上幾遍后面再遇到環(huán)形鏈表、雙向鏈表、跳表上手都會(huì)比身邊人快一大截。