學(xué)生時(shí)代第一次在課程作業(yè)里敲下“鏈表拼接.c”這個(gè)文件名時(shí)我心里想的是不就是把兩個(gè)鏈表首尾連起來(lái)嘛一個(gè)循環(huán)遍歷到尾節(jié)點(diǎn)然后把指針改一下能有多難可真當(dāng)我把這段代碼交上去、被導(dǎo)師指著段錯(cuò)誤問“你想過鏈表是空的嗎”之后我才明白越看似簡(jiǎn)單的操作底下埋的坑越是密集。組合兩個(gè)鏈表表面上是幾行指針賦值實(shí)際上牽扯到內(nèi)存所有權(quán)、邊界條件、結(jié)構(gòu)性設(shè)計(jì)甚至接口語(yǔ)義。今天我就把從“鏈表拼接.c”這個(gè)小文件里挖出來(lái)的東西系統(tǒng)地拆開講講。這篇東西適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的在校生、剛接觸C語(yǔ)言底層操作的開發(fā)者以及那些想確認(rèn)自己“拼接邏輯”沒有邊界漏洞的工程實(shí)踐者。別看標(biāo)題只是一個(gè)C源文件名背后涉及的內(nèi)容足夠你在面試或者Code Review的時(shí)候站穩(wěn)腳跟。1. 核心場(chǎng)景與整體設(shè)計(jì)思路在講代碼之前先想清楚到底什么樣的場(chǎng)景需要“鏈表拼接”不是所有把兩個(gè)節(jié)點(diǎn)串起來(lái)的操作都叫拼接。嚴(yán)格說(shuō)鏈表拼接(piecewise merge or concatenation)是指將兩個(gè)獨(dú)立鏈表的所有節(jié)點(diǎn)連接成一個(gè)完整鏈表且不產(chǎn)生新節(jié)點(diǎn)、不釋放任何原節(jié)點(diǎn)純粹是指針關(guān)系的重構(gòu)。這在多個(gè)場(chǎng)景都會(huì)出現(xiàn)緩沖區(qū)隊(duì)列合并比如網(wǎng)絡(luò)驅(qū)動(dòng)里接收隊(duì)列和空閑隊(duì)列要合并時(shí)。分塊數(shù)據(jù)的串聯(lián)把多個(gè)臨時(shí)分段數(shù)據(jù)鏈表合成一個(gè)完整數(shù)據(jù)流。內(nèi)存池整理把部分空閑塊鏈表合并成更大的空閑鏈。算法內(nèi)部的歸并輔助操作某些排序或劃分算法需要把兩個(gè)結(jié)果鏈表串接。在實(shí)際的“鏈表拼接.c”里最樸素的目標(biāo)就是實(shí)現(xiàn)一個(gè)函數(shù)比如struct node *concat(struct node *a, struct node *b)把鏈表a的尾節(jié)點(diǎn)指向鏈表b的首節(jié)點(diǎn)返回合并后的鏈表頭。聽起來(lái)簡(jiǎn)單但有一個(gè)核心決策點(diǎn)你必須想清楚就是誰(shuí)擁有這片內(nèi)存。如果你的函數(shù)只是“接”過來(lái)用后續(xù)由調(diào)用方統(tǒng)一釋放所有節(jié)點(diǎn)那你的拼接函數(shù)非常輕量只需要O(n)時(shí)間找到a的尾節(jié)點(diǎn)。如果你的函數(shù)還想對(duì)b做一些額外處理比如標(biāo)記來(lái)源、調(diào)整結(jié)構(gòu)那設(shè)計(jì)上就要預(yù)留遍歷鉤子。如果你還要考慮單獨(dú)的鏈表節(jié)點(diǎn)是否帶“頭節(jié)點(diǎn)”(dummy head)那拼接邏輯就得分開寫。從抽象結(jié)構(gòu)上看鏈表拼接在主存層面做的事情可以拆解成三個(gè)動(dòng)作定位鏈尾、修改指針、處理邊界。而所有實(shí)際開發(fā)中的麻煩幾乎都出在第三個(gè)動(dòng)作——邊界條件上?？真湵斫臃强真湵?、非空鏈表接空鏈表、兩個(gè)都空、a和b是同一個(gè)鏈表自拼接這種邊界沒想清楚代碼就是一把隨時(shí)崩的內(nèi)存炸彈。設(shè)計(jì)思路上我強(qiáng)烈建議你先把不變量寫出來(lái)。無(wú)論什么情況執(zhí)行完拼接操作后結(jié)果鏈表中的節(jié)點(diǎn)集合必須等于a和b節(jié)點(diǎn)集合的并集沒有任何一個(gè)節(jié)點(diǎn)被復(fù)制或被釋放如果是非循環(huán)鏈表則結(jié)果鏈表只能有一個(gè)尾節(jié)點(diǎn)且它的next為NULL。只要這兩個(gè)不變量擺在那你寫循環(huán)的時(shí)候就會(huì)不自覺去檢查邊界。這也是我后來(lái)從某位資深工程師那里偷師來(lái)的習(xí)慣先定不變量再寫實(shí)現(xiàn)。2. 樸素拼接實(shí)現(xiàn)與邊界條件解剖來(lái)看最傳統(tǒng)的單鏈表拼接實(shí)現(xiàn)也是“鏈表拼接.c”這個(gè)文件里大多數(shù)情況下被寫出來(lái)的第一版#include stdio.h #include stdlib.h struct node { int data; struct node *next; }; struct node *concat(struct node *a, struct node *b) { struct node *cur; if (a NULL) return b; if (b NULL) return a; cur a; while (cur-next ! NULL) cur cur-next; cur-next b; return a; }這段代碼是能用的但是你需要仔細(xì)品味它做了哪些事第一它快速處理了兩個(gè)空指針特例。如果a為空直接返回b這是合理的不變量要求的結(jié)果而且不需要任何遍歷和賦值。如果b為空直接返回a同樣成立。你把這兩種情況單獨(dú)摘出來(lái)說(shuō)明你已經(jīng)意識(shí)到尾指針判斷和空鏈表判斷不是一回事——一個(gè)判斷的是“結(jié)果結(jié)構(gòu)正確性”另一個(gè)判斷的是“遍歷終止條件”。第二主體循環(huán)while (cur-next ! NULL) cur cur-next;實(shí)際是在找尾節(jié)點(diǎn)它的執(zhí)行次數(shù)是a鏈表的節(jié)點(diǎn)數(shù)減一次。如果a有10000個(gè)節(jié)點(diǎn)它需要走9999步。時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)。第三指針賦值cur-next b;是整個(gè)函數(shù)的“實(shí)質(zhì)動(dòng)作”。傳入的b不需要遍歷它是b的頭指針?biāo)赃@一步是O(1)的。邊界問題在哪在于你沒有檢查a和b是否是同一個(gè)鏈表。假設(shè)concat(list, list)這個(gè)函數(shù)會(huì)先把cur走到list的尾節(jié)點(diǎn)然后執(zhí)行cur-next list于是鏈表瞬間變成循環(huán)鏈表。你返回的“新鏈表”再遍歷時(shí)永遠(yuǎn)走不到NULL死循環(huán)或越界訪問就在前方等著。另一個(gè)經(jīng)典邊界問題是b內(nèi)部是否有環(huán)。如果鏈表b內(nèi)部存在環(huán)那拼接后的鏈表自然也存在環(huán)而你的拼接函數(shù)并沒有義務(wù)去檢查環(huán)但如果調(diào)用方把它當(dāng)成正常鏈表用后果自擔(dān)。所以我建議在拼接函數(shù)里至少加一行注釋明確說(shuō)明“本函數(shù)不校驗(yàn)傳入鏈表是否有環(huán)調(diào)用方需保證鏈表結(jié)構(gòu)合法”這是接口契約的一部分。還有一個(gè)小細(xì)節(jié)值得注意返回值的語(yǔ)義。concat到底返回新鏈表的頭指針還是直接修改a的頭指針在純C里通常設(shè)計(jì)為返回合并后的鏈表頭。但是如果你把cur-next b之后直接返回a那么如果a是NULL時(shí)就只能返回b。像我例子里的寫法兩種空指針情況分開處理本質(zhì)上把返回值的語(yǔ)義統(tǒng)一為“合并后的表頭”這是非常清晰的做法。我們順便看一個(gè)常見的錯(cuò)誤版本struct node *bad_concat(struct node *a, struct node *b) { struct node *cur a; while (cur ! NULL) cur cur-next; cur-next b; // 運(yùn)行時(shí)崩潰 return a; }誤差在哪里循環(huán)結(jié)束后cur已經(jīng)變成NULL了你再對(duì)NULL做cur-next b空指針解引用直接段錯(cuò)誤。寫這個(gè)錯(cuò)誤的同學(xué)本質(zhì)上沒有分清楚“當(dāng)前節(jié)點(diǎn)”和“當(dāng)前節(jié)點(diǎn)的next”這兩種狀態(tài)。如果循環(huán)用的是“當(dāng)前節(jié)點(diǎn)是否為空”作為終止條件走到尾節(jié)點(diǎn)之后一定會(huì)多推一步——這是初學(xué)指針最常見的認(rèn)知裂隙。關(guān)于兩個(gè)空指針的判斷我再提一種更aggressive的寫法不管a、b是不是空統(tǒng)一用循環(huán)找尾然后用一個(gè)啞節(jié)點(diǎn)去接。但這樣會(huì)多做無(wú)謂的空鏈表判斷代碼也不見得更好懂。實(shí)際工程里我更喜歡顯式處理兩個(gè)特例因?yàn)檫@是邊界條件的“自我文檔化”——以后別人讀你的代碼第一眼就知道你考慮了空鏈表的情況這種可讀性價(jià)值往往比幾個(gè)判斷分支的開銷更有意義。3. 從O(n)到O(1)結(jié)構(gòu)性優(yōu)化的進(jìn)階思路只要你用的鏈表頭只有一個(gè)頭指針想拼接兩個(gè)鏈表必然得遍歷一條鏈找到尾節(jié)點(diǎn)。這是結(jié)構(gòu)性限制不是實(shí)現(xiàn)水平的問題。但如果你想在頻繁拼接的場(chǎng)景下把O(n)降下來(lái)辦法通常是改造鏈表的數(shù)據(jù)結(jié)構(gòu)讓它記錄尾指針。這里分享一個(gè)我自己用過的設(shè)計(jì)模式叫“尾指針鏈表”(tail linked list)struct list { struct node *head; struct node *tail; }; void append_list(struct list *dst, struct list *src) { if (src-head NULL) return; if (dst-head NULL) { dst-head src-head; dst-tail src-tail; } else { dst-tail-next src-head; dst-tail src-tail; } src-head src-tail NULL; // 防止雙重釋放/重復(fù)拼接 }這個(gè)改造的核心價(jià)值不只是把O(n)變成O(1)。它還引入了一個(gè)非常重要的工程語(yǔ)義轉(zhuǎn)移所有權(quán)。append_list執(zhí)行完畢后src的head和tail都被置為NULL了這意味著原鏈表b已經(jīng)“不屬于自己”了。后續(xù)如果想再對(duì)src做操作你寫出的代碼一定會(huì)先意識(shí)到“src已經(jīng)空了需要重新賦值”這就從根本上規(guī)避了那種對(duì)已拼接鏈表二次拼接導(dǎo)致的重復(fù)節(jié)點(diǎn)和環(huán)。而這個(gè)src-head src-tail NULL;的操作很多人第一次接觸時(shí)會(huì)覺得“這不是多余嗎反正也沒人再用b了”——恰恰相反這是防御性編程的精髓。你不置空它某次誤操作讓b再次拼接或被釋放時(shí)就會(huì)出現(xiàn)double-free或者一根節(jié)點(diǎn)同時(shí)歸屬兩條鏈的情況排查起來(lái)極其痛苦。真實(shí)項(xiàng)目里這種內(nèi)存歸屬二義性的bug比邏輯錯(cuò)誤難查十倍。尾指針方案的代價(jià)是鏈表的每個(gè)普通操作插入、刪除都要更新tail指針有些更新邏輯比單純的head指針復(fù)雜不少。比如刪除最后一個(gè)節(jié)點(diǎn)時(shí)你得從頭遍歷才能找到新的尾節(jié)點(diǎn)這時(shí)操作復(fù)雜度退回O(n)。這也是為什么它并不是萬(wàn)能藥而是適合“低頻修改高頻拼接和遍歷”的場(chǎng)景。再往深一層還可以考慮維護(hù)一個(gè)“鏈尾哨兵節(jié)點(diǎn)”。哨兵節(jié)點(diǎn)dummy tail讓每個(gè)鏈表都有一個(gè)始終存在的尾占位節(jié)點(diǎn)這樣拼接時(shí)統(tǒng)一走pre-next b-next的路徑省掉對(duì)空鏈表的特殊判斷。但哨兵節(jié)點(diǎn)帶來(lái)的問題是釋放鏈表時(shí)要處理這個(gè)額外節(jié)點(diǎn)遍歷時(shí)也要跳過它語(yǔ)義沒那么直接。工程上是否值得引入取決于你的代碼中有多少種操作需要面對(duì)“邊界空鏈表”的判斷。如果每種操作都要寫wrapper那哨兵思路省的是判斷次數(shù)成本是每次都要寫的跳過邏輯兩相權(quán)衡個(gè)人覺得在拼接密集的場(chǎng)景里尾指針方案更自然。4. 雙向鏈表與雙向循環(huán)鏈表的拼接差異很多講鏈表拼接的資料只講單向鏈表。但實(shí)際大多數(shù)帶刪除需求的項(xiàng)目用的是雙向鏈表。拼接難度在雙向鏈表里翻倍了因?yàn)槟悴还庖薷膎ext還得修改prev而且要保證新鏈表的prev鏈條在每個(gè)節(jié)點(diǎn)上都自洽。先看最經(jīng)典的雙向鏈表拼接邏輯。假設(shè)a的尾節(jié)點(diǎn)是a_tailb的頭節(jié)點(diǎn)是b_head那你要同時(shí)執(zhí)行a_tail-next b_head; b_head-prev a_tail;僅此而已嗎不是。你還需要處理一個(gè)很容易被忽略的點(diǎn)a原來(lái)的尾節(jié)點(diǎn)的next曾經(jīng)是NULL它作為一個(gè)“尾標(biāo)識(shí)”存在于鏈表中。拼接后a_tail不再是尾節(jié)點(diǎn)你的代碼如果還有別的地方依賴“next為NULL即尾節(jié)點(diǎn)”的判斷就要立刻失效。這也提示你雙向鏈表拼接參與的判斷邏輯往往分散在鏈結(jié)構(gòu)內(nèi)部全局搜一遍所有“尋找尾節(jié)點(diǎn)”或“檢查是否尾節(jié)點(diǎn)”的地方是必須的。還有一個(gè)細(xì)節(jié)是在雙向鏈表里拼接操作必須先保存b的原尾節(jié)點(diǎn)。如果你在操作中先修改了b_head-prev而后面還想找b的尾節(jié)點(diǎn)就需要從頭遍歷了。所以合理的拼接順序是先找到a尾節(jié)點(diǎn)。先找到b尾節(jié)點(diǎn)或使用結(jié)構(gòu)體中保存的tail指針。做一個(gè)“假想連接”但不急著寫指針。統(tǒng)一執(zhí)行a_tail-next b_head; b_head-prev a_tail; b_tail-next NULL;更新鏈表的head/tail元數(shù)據(jù)。這種“先找全、再開寫”的二段式做法能有效降低操作中間態(tài)時(shí)指針錯(cuò)亂的概率。你想想如果你先執(zhí)行a_tail-next b_head;然后突然程序被中斷比如多線程環(huán)境此時(shí)鏈表a已經(jīng)多了一條尾巴延伸進(jìn)b而b的內(nèi)部還沒調(diào)整完整個(gè)結(jié)構(gòu)處于半崩潰狀態(tài)。工程實(shí)踐中多線程環(huán)境里對(duì)鏈表的操作要盡量保證“原子變更共享指針”的級(jí)別哪怕用鎖也要盡量縮短鎖的臨界區(qū)。雙向循環(huán)鏈表比如內(nèi)核里常見的環(huán)形雙向鏈表的拼接又有不同。所謂循環(huán)鏈表是指尾節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)頭節(jié)點(diǎn)的prev指向尾節(jié)點(diǎn)。拼接兩個(gè)循環(huán)鏈表時(shí)最經(jīng)典的做法是拼成一個(gè)大的環(huán)不再區(qū)分a、b的首尾。邏輯上相當(dāng)于把b環(huán)拆開插入a環(huán)中// 核心操作示意 struct node *a_head ...; struct node *a_tail a_head-prev; struct node *b_head ...; struct node *b_tail b_head-prev; a_tail-next b_head; b_head-prev a_tail; b_tail-next a_head; a_head-prev b_tail;這個(gè)操作里所有賦值都是O(1)完成的因?yàn)槟憷玫氖茄h(huán)鏈表本身自帶的頭尾信息——頭節(jié)點(diǎn)的prev就是尾節(jié)點(diǎn)不需要遍歷。我第一次看到這個(gè)操作時(shí)覺得特別驚艷它把指針操作的對(duì)稱性展示得淋漓盡致每個(gè)節(jié)點(diǎn)在拼接過程中正好被修改一次next和一次prev內(nèi)外兩條鏈都閉合了。如果你以后在面試?yán)镉龅健叭绾魏喜蓚€(gè)循環(huán)雙向鏈表”直接把這個(gè)四步操作寫出來(lái)面試官基本就能分辨出你真正理解鏈表的環(huán)形結(jié)構(gòu)而不是在背代碼。但循環(huán)鏈表也有它自己的坑拼接后你很難找到一個(gè)“自然的NULL終點(diǎn)”作為遍歷終止判據(jù)你必須時(shí)刻記錄起始節(jié)點(diǎn)并通過“回到起點(diǎn)”來(lái)判斷遍歷是否結(jié)束。如果在循環(huán)鏈表里錯(cuò)誤地使用while (cur ! NULL)來(lái)遍歷直接就是一個(gè)死循環(huán)。所以在循環(huán)鏈表拼接的代碼里約定好“我們以a_head作為新鏈表的統(tǒng)一入口”是很重要的這相當(dāng)于給新環(huán)錨定了一個(gè)坐標(biāo)系。5. 內(nèi)核鏈表list_head的拼接設(shè)計(jì)思路聊到鏈表拼接不可能繞開Linux內(nèi)核里那套著名的struct list_head設(shè)計(jì)。雖然普通應(yīng)用層C代碼未必直接使用它但它的設(shè)計(jì)思想對(duì)理解“拼接”這個(gè)操作非常有啟發(fā)——因?yàn)樗选肮?jié)點(diǎn)”和“數(shù)據(jù)”徹底分離了。struct list_head { struct list_head *next, *prev; };你的業(yè)務(wù)結(jié)構(gòu)體里嵌一個(gè)struct list_head成員然后通過container_of宏從這個(gè)成員指針反推出包含它的業(yè)務(wù)結(jié)構(gòu)體指針。這種設(shè)計(jì)下拼接兩個(gè)鏈表拼的只是一堆list_head結(jié)構(gòu)之間的鏈接關(guān)系與具體數(shù)據(jù)無(wú)關(guān)。而list_splice這個(gè)操作某資深內(nèi)核開發(fā)者提供了一個(gè)極具對(duì)稱美的實(shí)現(xiàn)。我在這里給出一個(gè)簡(jiǎn)化后的注釋版本static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next) { struct list_head *first list-next; struct list_head *last list-prev; first-prev prev; prev-next first; last-next next; next-prev last; }這段代碼做的事本質(zhì)上就是把list這條鏈表無(wú)縫插到prev和next之間。它不關(guān)心list是否是空鏈表空鏈表的first和last都指向自己操作仍然成立也不關(guān)心prev和next是否屬于同一條鏈表幾乎把“邊界情況”這個(gè)導(dǎo)致普通的鏈表拼接代碼出bug的根源給消滅了。因?yàn)閘ist_head本身是一個(gè)環(huán)形雙向鏈表空鏈表并不是“NULL指針”而是“next和prev都指向自身”所以你根本不需要寫if (a NULL) return b;這種特判。對(duì)了內(nèi)核鏈表還有一個(gè)精巧設(shè)計(jì)在空鏈表中next和prev都指向鏈表頭自身。這樣拼接函數(shù)里的所有賦值都是有效操作不存在空指針解引用的問題。所謂“空轉(zhuǎn)”的邊界問題被數(shù)據(jù)結(jié)構(gòu)本身的自指特質(zhì)消解掉了這是非常高級(jí)的設(shè)計(jì)。如果在應(yīng)用層做業(yè)務(wù)鏈表拼接我會(huì)推薦借鑒list_splice的這種“三段式”寫法定義first和last然后先連first再連last最后再串成一個(gè)整體。它天然把修改步驟拆散方便你在調(diào)試時(shí)把鏈條在邏輯上一個(gè)一個(gè)接起來(lái)。而最常見的錯(cuò)誤就是不分first/last、直接“一步到位”地連續(xù)改多個(gè)指針結(jié)果某一處順手寫錯(cuò)全部節(jié)點(diǎn)都變成了野指針。6. 實(shí)際調(diào)試經(jīng)驗(yàn)與常見問題速查文章寫到最后一部分必須聊聊真實(shí)調(diào)試中遇到的那些“看上去毫無(wú)邏輯”的崩潰現(xiàn)場(chǎng)。鏈表拼接的典型癥狀基本逃不出段錯(cuò)誤(Segmentation Fault)、死循環(huán)、丟數(shù)據(jù)和雙倍釋放。下面我把排查經(jīng)驗(yàn)按概率列一下。段錯(cuò)誤大概率是空指針解引用。常見誘因頭指針未初始化拼接時(shí)遍歷到NULL然后又用NULL做賦值或者鏈表結(jié)構(gòu)里存在未被正確連接的懸掛節(jié)點(diǎn)導(dǎo)致遍歷時(shí)跳到一個(gè)被釋放過、隨即指針被篡改的垃圾內(nèi)存。排查建議是先不要跑程序在紙上畫出拼接前后的指針關(guān)系圖對(duì)每個(gè)-next賦值確認(rèn)賦值的右側(cè)不是NULL除非語(yǔ)義上需要。另外一定要把鏈表節(jié)點(diǎn)的內(nèi)存打上魔法數(shù)字比如分配時(shí)把每個(gè)節(jié)點(diǎn)內(nèi)存填充成0xCD這樣一旦跳到未初始化的節(jié)點(diǎn)會(huì)立刻通過打印值發(fā)現(xiàn)。死循環(huán)大多數(shù)情況是finally一個(gè)節(jié)點(diǎn)沒有正確設(shè)置next NULL。循環(huán)鏈表的拼接忘了收口或者自拼接a接a后變成環(huán)都會(huì)死循環(huán)。怎么排查寫一個(gè)調(diào)試函數(shù)遍歷鏈表最多1000步如果沒到NULL就強(qiáng)制中斷并打日志for (i 0; i 1000 cur; i) cur cur-next; if (cur) printf(loop detected\n);。這個(gè)小工具函數(shù)是我排查鏈表環(huán)的萬(wàn)金油建議收藏進(jìn)你的調(diào)試工具庫(kù)。丟數(shù)據(jù)拼接后某些節(jié)點(diǎn)找不到了。最典型的原因多個(gè)指針指向同一塊舊鏈表頭后續(xù)一個(gè)指針被覆蓋另一個(gè)沒有更新。比如你有一個(gè)全局變量保存了鏈表b的頭指針拼接完成后忘記更新它為NULL或新鏈表的某個(gè)位置往后再通過它訪問b的舊節(jié)點(diǎn)就會(huì)讀到已經(jīng)改過的next/prev結(jié)構(gòu)錯(cuò)亂仿佛數(shù)據(jù)“丟了”。本質(zhì)上不是數(shù)據(jù)丟了而是你的指針元數(shù)據(jù)沒同步。解決方案在我的經(jīng)驗(yàn)里只有一個(gè)拼接完成的一剎那所有舊的入口指針必須被清理或重新定位絕不給后續(xù)代碼留有“繼續(xù)從舊入口訪問”的機(jī)會(huì)。雙重釋放通常是b節(jié)點(diǎn)的所有權(quán)在拼接后依舊被外部持有外部代碼以為b鏈表還能獨(dú)立釋放拼完后又對(duì)b執(zhí)行一次free遍歷。這個(gè)問題在純C代碼里沒有自動(dòng)回收機(jī)制兜底只能靠紀(jì)律約束在拼接完成后立即把b的鏈表頭或list結(jié)構(gòu)置為空鏈表狀態(tài)。比如你持有struct node *b_head拼接之后立刻執(zhí)行b_head NULL;這樣任何后續(xù)釋放操作都因?yàn)闊o(wú)法訪問原鏈表而“不得不”重新確認(rèn)對(duì)象兩三次一錯(cuò)你自然會(huì)發(fā)現(xiàn)那個(gè)被置空的變量處在哪個(gè)鏈路中。我給自己的規(guī)則是鏈表拼接操作永遠(yuǎn)不要返回“兩個(gè)鏈表都有主”的狀態(tài)要么是a主b空要么是b主a空不存在共同持有。一個(gè)特殊坑拼接后的遍歷權(quán)限拼接完的鏈表如果給其他線程用而那個(gè)線程還在拿舊鏈表b的局部變量緩存做遍歷就會(huì)產(chǎn)生iterator invalidation的問題。兩種解決思路一是拼接前鎖住兩個(gè)鏈表拼接后所有要遍歷的人重新從新的head抓取入口二是干脆讓鏈表操作全部串行化犧牲一點(diǎn)并發(fā)性能換正確性。我個(gè)人在共享數(shù)據(jù)密集的項(xiàng)目里更傾向于前者。癥狀大概率原因建議排查手段段錯(cuò)誤空指針/野指針/未初始化畫指針圖魔法數(shù)字填充逐步打印死循環(huán)尾節(jié)點(diǎn)未置NULL/環(huán)設(shè)置“最多遍歷N步”的調(diào)試函數(shù)丟數(shù)據(jù)舊入口指針未更新拼接后統(tǒng)一清掉所有舊入口雙重釋放所有權(quán)歸屬不清拼接時(shí)立即把源鏈表的入口清空多線程錯(cuò)亂并發(fā)訪問/迭代器失效上鎖拼接后重新獲取入口調(diào)試鏈表拼接時(shí)不光要會(huì)看GDB的print更要養(yǎng)成“先結(jié)構(gòu)、后邏輯”的診斷順序。也就是說(shuō)先確認(rèn)鏈表本身的結(jié)構(gòu)形態(tài)長(zhǎng)度、是否成環(huán)、每個(gè)節(jié)點(diǎn)指針的值再去看拼接那幾行代碼到底改對(duì)了沒有。我經(jīng)常遇到的情況是出錯(cuò)代碼不在拼接函數(shù)本身而在于拼接之前某個(gè)節(jié)點(diǎn)就被錯(cuò)誤地多連了一次。如果你一上來(lái)就盯拼接代碼看反而半天找不到問題。7. 把鏈表拼接寫成一個(gè)“可復(fù)用組件”如果你不止一次在項(xiàng)目里寫鏈表拼接就不要滿足于每次從頭敲一遍了。把拼接邏輯沉淀成一個(gè)可復(fù)用組件是我認(rèn)為這一整篇文章里最有工程價(jià)值的建議。要做到這點(diǎn)關(guān)鍵不在于抽象函數(shù)而在于抽象“鏈表結(jié)構(gòu)”。一個(gè)將來(lái)可以被多次復(fù)用的拼接模塊至少包含這些聲明一個(gè)表示鏈表的句柄包括head和tail。一個(gè)負(fù)責(zé)尋找尾節(jié)點(diǎn)的輔助函數(shù)。一個(gè)負(fù)責(zé)拼接的主函數(shù)接收兩個(gè)句柄返回新句柄。一個(gè)負(fù)責(zé)校驗(yàn)鏈表結(jié)構(gòu)合法性的調(diào)試輔助函數(shù)。一個(gè)負(fù)責(zé)銷毀鏈表的函數(shù)避免內(nèi)存泄漏。你在“鏈表拼接.c”里封裝的函數(shù)應(yīng)該讓調(diào)用方幾乎不可能誤用。我建議所有對(duì)外接口都以句柄結(jié)構(gòu)體指針為參數(shù)不要直接暴露裸節(jié)點(diǎn)指針。這樣你可以在拼接函數(shù)內(nèi)部統(tǒng)一檢查句柄里維護(hù)的tail指針是否和實(shí)際遍歷到的尾節(jié)點(diǎn)一致及時(shí)發(fā)現(xiàn)鏈表結(jié)構(gòu)損壞。// 偽代碼風(fēng)格示例 struct linked_list { struct node *head; struct node *tail; size_t length; }; struct linked_list *list_merge(struct linked_list *dst, struct linked_list *src);這個(gè)組件一旦穩(wěn)定下來(lái)你在項(xiàng)目中其他地方用鏈表時(shí)就不用再反復(fù)琢磨邊界條件了。個(gè)人經(jīng)驗(yàn)把“鏈表代碼”從“業(yè)務(wù)代碼”里剝離出來(lái)哪怕只是一個(gè)很小的工具模塊對(duì)項(xiàng)目的長(zhǎng)期維護(hù)收益都是非常可觀的。你會(huì)發(fā)現(xiàn)自己少了很多半夜修buffer overflow的時(shí)間。我在做某次模塊開發(fā)時(shí)就是因?yàn)榘哑唇雍瘮?shù)單獨(dú)抽出來(lái)并加了邊界斷言后面單元測(cè)試直接把空鏈表拼接、自拼接、大鏈表接小鏈表、雙向鏈表的頭尾拼接、循環(huán)鏈表的收口等等case全部掃了一遍才敢把它交到集成測(cè)試環(huán)節(jié)。那種“早就料到這里會(huì)炸、所以提前填好防御”的安全感是寫出高質(zhì)量C代碼很重要的一部分心態(tài)。鏈表拼接這個(gè)小操作背后反映的不止是指針技巧更是你對(duì)內(nèi)存組織結(jié)構(gòu)的理解深度。把邊界條件、所有權(quán)語(yǔ)義、結(jié)構(gòu)不變量都想清楚你的代碼也就不再是那些一跑就崩的作業(yè)而是能真正進(jìn)生產(chǎn)環(huán)境的模塊了。