看多了網(wǎng)上那種“數(shù)據(jù)結(jié)構(gòu)三要素背下來(lái)鏈表操作背下來(lái)”的學(xué)習(xí)方法我想說(shuō)一句實(shí)在話鏈表操作根本不是背代碼的活。如果一開(kāi)始就用數(shù)據(jù)結(jié)構(gòu)三要素的視角去拆解你會(huì)發(fā)現(xiàn)鏈表那套“增刪改查”其實(shí)是順著邏輯自己長(zhǎng)出來(lái)的。這篇文章我花點(diǎn)時(shí)間把《數(shù)據(jù)結(jié)構(gòu)三要素解析 鏈表的12個(gè)基礎(chǔ)操作代碼詳解》這個(gè)主題徹底展開(kāi)結(jié)合我早年剛啃數(shù)據(jù)結(jié)構(gòu)時(shí)踩過(guò)的坑把“既要懂原理又要能寫(xiě)代碼”這條路走通。不管你是正準(zhǔn)備期末的在校生還是想補(bǔ)內(nèi)功的轉(zhuǎn)行開(kāi)發(fā)者這篇都值得從頭到尾看完。1. 數(shù)據(jù)結(jié)構(gòu)三要素先跳出來(lái)再鉆進(jìn)去很多人在學(xué)鏈表之前其實(shí)沒(méi)弄明白“數(shù)據(jù)結(jié)構(gòu)到底在學(xué)什么”。我在初學(xué)階段也干過(guò)蠢事——拿著教材從頭背到尾定義、特性、時(shí)間復(fù)雜度背得滾瓜爛熟結(jié)果一到寫(xiě)代碼就抓瞎。后來(lái)一位算法方向的前輩點(diǎn)了我一句“你先把數(shù)據(jù)結(jié)構(gòu)的三要素搞清楚你就知道每段代碼在干嘛了。”1.1 邏輯結(jié)構(gòu)數(shù)據(jù)之間的關(guān)系是什么三要素的第一條是邏輯結(jié)構(gòu)。所謂邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間存在什么關(guān)系。這個(gè)關(guān)系是抽象的不管你用數(shù)組、鏈表還是樹(shù)形結(jié)構(gòu)去實(shí)現(xiàn)邏輯關(guān)系本身是獨(dú)立的。鏈表對(duì)應(yīng)的邏輯結(jié)構(gòu)是線性表它的特點(diǎn)是數(shù)據(jù)元素之間存在一對(duì)一的前驅(qū)后繼關(guān)系。說(shuō)得直白一點(diǎn)就是每個(gè)節(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼頭部節(jié)點(diǎn)沒(méi)有前驅(qū)尾部節(jié)點(diǎn)沒(méi)有后繼。當(dāng)初理解“邏輯結(jié)構(gòu)”這個(gè)概念的時(shí)候我用了一個(gè)特別生活化的類比排隊(duì)買(mǎi)奶茶。你前面那個(gè)人是你的直接前驅(qū)你后面那個(gè)人是你的直接后繼隊(duì)首沒(méi)有前驅(qū)隊(duì)尾沒(méi)有后繼。這個(gè)前后關(guān)系就是線性表的邏輯結(jié)構(gòu)。至于大家是站在一條水泥地上的隊(duì)伍里數(shù)組還是每個(gè)人手里拿著前一個(gè)人的衣角串成一串鏈表那是存儲(chǔ)結(jié)構(gòu)的事邏輯關(guān)系沒(méi)變。1.2 存儲(chǔ)結(jié)構(gòu)關(guān)系如何落到內(nèi)存三要素的第二條是存儲(chǔ)結(jié)構(gòu)也叫物理結(jié)構(gòu)。它解決的是“邏輯關(guān)系在計(jì)算機(jī)里怎么表示”的問(wèn)題。線性表有兩種經(jīng)典的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)就是數(shù)組邏輯相鄰的元素在內(nèi)存里也物理相鄰。它的特點(diǎn)是“隨機(jī)存取”——給一個(gè)下標(biāo)就能直接算出地址訪問(wèn)第5個(gè)元素的代價(jià)和訪問(wèn)第5000個(gè)元素是一樣的。但它的短板也很明顯插入和刪除要搬動(dòng)大量元素而且需要一整塊連續(xù)內(nèi)存。鏈?zhǔn)酱鎯?chǔ)就是鏈表。它允許元素在內(nèi)存里東一個(gè)西一個(gè)每個(gè)節(jié)點(diǎn)除了存數(shù)據(jù)還要存一個(gè)指針指向下一個(gè)節(jié)點(diǎn)的地址。這樣邏輯相鄰的元素不需要物理相鄰靠指針就能串起來(lái)。付出的代價(jià)是不能“隨機(jī)存取”想找第5個(gè)節(jié)點(diǎn)必須從頭往后一個(gè)個(gè)跳。兩者對(duì)比下來(lái)一句話就能說(shuō)清數(shù)組是“物理相鄰換隨機(jī)訪問(wèn)”鏈表是“物理離散換靈活增刪”。1.3 數(shù)據(jù)運(yùn)算一切操作的入口定義三要素的第三條是數(shù)據(jù)運(yùn)算也就是針對(duì)這個(gè)結(jié)構(gòu)我們要支持哪些操作。在。在教材層面運(yùn)算包括建立、銷(xiāo)毀、查找、插入、刪除、修改、遍歷、求長(zhǎng)度、判空這些基本動(dòng)作。學(xué)習(xí)的關(guān)鍵在于這些運(yùn)算不是孤立的背代碼它們?nèi)拷⒃谇皟蓚€(gè)要素之上。比如“插入”這個(gè)運(yùn)算在數(shù)組里是先移動(dòng)元素再放入在鏈表里是改兩個(gè)指針——為什么不一樣就是因?yàn)榇鎯?chǔ)結(jié)構(gòu)不同。搞清楚了存儲(chǔ)結(jié)構(gòu)運(yùn)算方式就是順理成章的事。我經(jīng)常遇到讀者問(wèn)我“為什么鏈表插入的時(shí)間復(fù)雜度是O(1)但實(shí)際寫(xiě)代碼好像還要先查找到那個(gè)位置”這個(gè)問(wèn)題問(wèn)得很好。要解釋清楚就必須區(qū)分兩種操作如果你已經(jīng)有了當(dāng)前節(jié)點(diǎn)的指針那插入一個(gè)新節(jié)點(diǎn)確實(shí)是O(1)但如果你只有位置序號(hào)第一步還要從頭遍歷找節(jié)點(diǎn)遍歷是O(n)所以“按位置插入”的總代價(jià)是O(n)。這就是數(shù)據(jù)運(yùn)算和邏輯結(jié)構(gòu)交織在一起的典型案例。有了這三要素的框架再看鏈表的所有基礎(chǔ)操作你會(huì)發(fā)現(xiàn)每一段代碼都有它的“因”。下面我把整個(gè)鏈表操作的代碼工程拆開(kāi)來(lái)講所有代碼均基于C語(yǔ)言這是數(shù)據(jù)結(jié)構(gòu)教材最常見(jiàn)也最便于理解指針操作的載體。2. 鏈表操作前的三道基礎(chǔ)題結(jié)構(gòu)體設(shè)計(jì)、頭結(jié)點(diǎn)選擇、公共約定在動(dòng)手寫(xiě)12個(gè)基礎(chǔ)操作之前必須先做三件事。很多初學(xué)者代碼寫(xiě)了半天編譯不過(guò)或者各種段錯(cuò)誤90%的問(wèn)題出在這三個(gè)前置選擇上。2.1 結(jié)構(gòu)體的定義與頭結(jié)點(diǎn)之爭(zhēng)C語(yǔ)言里單鏈表節(jié)點(diǎn)的定義是這樣的// 單鏈表節(jié)點(diǎn)定義 typedef struct LNode { int data; // 數(shù)據(jù)域這里以int為例 struct LNode *next; // 指針域指向下一個(gè)節(jié)點(diǎn) } LNode; // 使用別名簡(jiǎn)化聲明LNode* 表示指向節(jié)點(diǎn)的指針這段代碼本身沒(méi)有太多懸念。真正的分歧在“要不要頭結(jié)點(diǎn)”這個(gè)問(wèn)題上。頭結(jié)點(diǎn)注意不是頭指針是鏈表第一個(gè)節(jié)點(diǎn)之前額外增加的一個(gè)節(jié)點(diǎn)。它不存有效數(shù)據(jù)placeholder只是為了統(tǒng)一操作邏輯。帶頭結(jié)點(diǎn)的鏈表頭指針永遠(yuǎn)指向那個(gè)哨兵節(jié)點(diǎn)不帶頭結(jié)點(diǎn)的鏈表頭指針直接指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)。我從實(shí)際工程經(jīng)驗(yàn)和考試兩個(gè)角度看都建議帶頭結(jié)點(diǎn)。理由很簡(jiǎn)單帶頭結(jié)點(diǎn)之后在頭部插入和刪除就不需要特殊對(duì)待了整個(gè)鏈表的所有插入刪除邏輯可以完全統(tǒng)一。這對(duì)代碼的健壯性和可讀性都有很大提升。2.2 12個(gè)基礎(chǔ)操作怎么選出來(lái)的既然標(biāo)題叫“12個(gè)基礎(chǔ)操作”我先列個(gè)清單。對(duì)單鏈表來(lái)說(shuō)真正“基礎(chǔ)”的操作圍繞增刪改查四條線展開(kāi)初始化鏈表創(chuàng)建帶頭結(jié)點(diǎn)的空鏈表判斷鏈表是否為空求鏈表長(zhǎng)度按位查找找第i個(gè)節(jié)點(diǎn)按值查找找第一個(gè)值等于x的節(jié)點(diǎn)頭插法插入節(jié)點(diǎn)尾插法插入節(jié)點(diǎn)指定位置插入節(jié)點(diǎn)按位刪除節(jié)點(diǎn)按值刪除節(jié)點(diǎn)修改指定位置節(jié)點(diǎn)的值遍歷打印鏈表這12個(gè)操作覆蓋了一個(gè)基本線性表的所有日常需求。你會(huì)發(fā)現(xiàn)它們之間有清晰的依賴關(guān)系查找是后面插入刪除的基礎(chǔ)長(zhǎng)度和判空是通用工具頭尾插入是構(gòu)造鏈表的兩種主要方式。先掌握它們后面的逆轉(zhuǎn)、排序、合并等進(jìn)階操作才能順手。2.3 每個(gè)操作都要遵守的公共約定在寫(xiě)任何一個(gè)操作之前先定下約定。不然12個(gè)函數(shù)各有各的返回值風(fēng)格寫(xiě)著寫(xiě)著就亂了。我的約定如下函數(shù)內(nèi)部操作失敗返回0或-1成功返回1布爾語(yǔ)義。查找類的函數(shù)找到返回節(jié)點(diǎn)指針找不到返回NULL。傳入的頭指針如果為NULL直接返回失敗或NULL不繼續(xù)執(zhí)行。位置參數(shù)從1開(kāi)始計(jì)數(shù)這是教材和大多數(shù)考試的統(tǒng)一規(guī)則避免和數(shù)組下標(biāo)混淆。這些約定看起來(lái)瑣碎但它保證了12個(gè)函數(shù)在組合調(diào)用的時(shí)候邏輯一致。比如“在第i個(gè)位置插入”內(nèi)部會(huì)先調(diào)“按位查找第i-1個(gè)節(jié)點(diǎn)”兩者通過(guò)位置語(yǔ)義保持一致就很少出錯(cuò)。3. 增刪改查四類基礎(chǔ)操作的代碼拆解前置工作做完開(kāi)始寫(xiě)核心代碼。這一節(jié)是全文的重頭戲我會(huì)把12個(gè)操作按依賴關(guān)系層層拆開(kāi)。每一段代碼都帶注釋注釋里寫(xiě)清“為什么這么做”。3.1 按位查找與按值查找一切操作的地基查找操作是整個(gè)鏈表的基石。插入和刪除的前置步驟基本都是“找到目標(biāo)節(jié)點(diǎn)的前驅(qū)”。按位查找的代碼// 按位查找返回第i個(gè)節(jié)點(diǎn)的指針 // 約定i從1開(kāi)始計(jì)數(shù)不包括頭結(jié)點(diǎn) LNode* GetElem(LNode L, int i) { if (i 1) { return NULL; // 位置不合法 } LNode *p L; // p指向當(dāng)前掃描到的節(jié)點(diǎn)從第0個(gè)頭結(jié)點(diǎn)開(kāi)始 int j 0; // j記錄p是第幾個(gè)節(jié)點(diǎn) while (p ! NULL j i) { p p-next; j; } // 如果p為NULL說(shuō)明i超出了鏈表長(zhǎng)度否則p就是第i個(gè)節(jié)點(diǎn) return p; }這里有個(gè)細(xì)節(jié)值得說(shuō)透為什么從第0個(gè)頭結(jié)點(diǎn)而不是第1個(gè)節(jié)點(diǎn)開(kāi)始跳因?yàn)椴檎业趇個(gè)節(jié)點(diǎn)需要移動(dòng)i次。帶頭結(jié)點(diǎn)的情況下從head出發(fā)走i步正好停在第i個(gè)節(jié)點(diǎn)上。這個(gè)“偏移量”思維是整個(gè)鏈表操作最核心的數(shù)學(xué)基礎(chǔ)。按值查找的代碼// 按值查找返回第一個(gè)值為x的節(jié)點(diǎn)指針 LNode* LocateElem(LNode L, int x) { LNode *p L-next; // 從第一個(gè)數(shù)據(jù)節(jié)點(diǎn)開(kāi)始 while (p ! NULL) { if (p-data x) { return p; // 找到返回指針 } p p-next; } return NULL; // 沒(méi)找到 }這段代碼沒(méi)有什么高深技巧但注意一點(diǎn)遍歷時(shí)不要把p移動(dòng)完再判斷要邊移動(dòng)邊判斷邊退出。習(xí)慣了循環(huán)寫(xiě)全量的同學(xué)很容易把結(jié)束條件寫(xiě)成遍歷完整個(gè)鏈表白白浪費(fèi)CPU還丟失了“第一個(gè)匹配項(xiàng)”的語(yǔ)義。3.2 頭插法、尾插法與指定位置插入三個(gè)層次的插入插入操作是鏈表靈活性的集中體現(xiàn)。我按“頭、尾、指定位置”三個(gè)層次來(lái)講。頭插法在頭結(jié)點(diǎn)后面直接插入新節(jié)點(diǎn)// 頭插法在頭結(jié)點(diǎn)后插入新節(jié)點(diǎn)插到鏈表最前面 int HeadInsert(LNode *L, int x) { LNode *s (LNode*)malloc(sizeof(LNode)); // 創(chuàng)建新節(jié)點(diǎn) if (s NULL) { return 0; // 內(nèi)存分配失敗 } s-data x; s-next L-next; // 新節(jié)點(diǎn)指向原來(lái)的第一個(gè)數(shù)據(jù)節(jié)點(diǎn) L-next s; // 頭結(jié)點(diǎn)指向新節(jié)點(diǎn) return 1; }這段代碼的講解難點(diǎn)在于兩行指針操作的順序。很多人初學(xué)時(shí)容易寫(xiě)成“先把L-next賦給s-next再讓L-next指向s”——其實(shí)順序是反的。這里有個(gè)口訣先接后面的線再斷前面的線。先讓新節(jié)點(diǎn)的next指向原第一個(gè)節(jié)點(diǎn)再讓頭結(jié)點(diǎn)的next指向新節(jié)點(diǎn)順序絕對(duì)不能反。如果先執(zhí)行L-next s原來(lái)的第一個(gè)節(jié)點(diǎn)就丟了整條鏈表從中斷開(kāi)。尾插法在鏈表尾部接上新節(jié)點(diǎn)// 尾插法在鏈表末尾插入新節(jié)點(diǎn) int TailInsert(LNode *L, int x) { LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return 0; } s-data x; s-next NULL; // 找到當(dāng)前尾節(jié)點(diǎn) LNode *p L; while (p-next ! NULL) { p p-next; } p-next s; // 尾節(jié)點(diǎn)指向新節(jié)點(diǎn)新節(jié)點(diǎn)成為新的尾節(jié)點(diǎn) return 1; }尾插法的時(shí)間復(fù)雜度是O(n)因?yàn)槊看味家獜念^遍歷到尾。大量使用尾插法構(gòu)造鏈表時(shí)更高效的做法是設(shè)置一個(gè)尾指針。實(shí)際構(gòu)造鏈表時(shí)也常常讓用戶自定義建表方式這里為了操作展示保持簡(jiǎn)單沒(méi)有優(yōu)化成尾指針形式如果你要寫(xiě)一個(gè)高頻插入的模塊務(wù)必自己加尾巴指針。指定位置插入這算是插入操作的綜合應(yīng)用了// 指定位置插入在第i個(gè)位置插入新節(jié)點(diǎn)i從1開(kāi)始 int InsertAt(LNode *L, int i, int x) { LNode *p GetElem(L, i - 1); // 找到第i-1個(gè)節(jié)點(diǎn)它是新節(jié)點(diǎn)的前驅(qū) if (p NULL) { return 0; // 前驅(qū)不存在位置非法 } LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) { return 0; } s-data x; s-next p-next; // 先接后面的線 p-next s; // 再斷前面的線 return 1; }這個(gè)操作把“按位查找”和“插入”組合起來(lái)了。注意細(xì)節(jié)調(diào)用GetElem找的是第i-1個(gè)節(jié)點(diǎn)。為什么不是第i個(gè)因?yàn)椴迦氲谋举|(zhì)是在第i-1個(gè)節(jié)點(diǎn)和第i個(gè)節(jié)點(diǎn)之間塞一個(gè)節(jié)點(diǎn)你手里需要有前驅(qū)節(jié)點(diǎn)的指針。這個(gè)“找前驅(qū)”的思維后邊的刪除操作也會(huì)用到屬于鏈表操作里最關(guān)鍵的思維模式之一。3.3 按位刪除與按值刪除先接后斷的完整應(yīng)用刪除操作的代碼量不大但它是考察指針操作理解程度的試金石。按位刪除// 按位刪除刪除第i個(gè)節(jié)點(diǎn)并用e返回其數(shù)據(jù) int DeleteAt(LNode *L, int i, int *e) { if (i 1) { return 0; } LNode *p GetElem(L, i - 1); // 找到被刪節(jié)點(diǎn)的前驅(qū) if (p NULL || p-next NULL) { return 0; // 前驅(qū)不存在或沒(méi)有第i個(gè)節(jié)點(diǎn) } LNode *q p-next; // q指向被刪除的節(jié)點(diǎn) *e q-data; // 帶回?cái)?shù)據(jù) p-next q-next; // 前驅(qū)直接跨過(guò)q連到q的下一個(gè)節(jié)點(diǎn) free(q); // 釋放被刪除節(jié)點(diǎn)的內(nèi)存 return 1; }這里同樣遵循“先接后斷”的原則但刪操作里是先斷前面的線p-next q-next再釋放節(jié)點(diǎn)。注意一個(gè)小細(xì)節(jié)調(diào)用GetElem找第i-1個(gè)節(jié)點(diǎn)找到后還要再確認(rèn)p-next ! NULL因?yàn)橛锌赡躨比鏈表長(zhǎng)度大1此時(shí)p不是NULL但p-next是NULL表示沒(méi)有第i個(gè)節(jié)點(diǎn)刪無(wú)可刪。按值刪除// 按值刪除刪除第一個(gè)值等于x的節(jié)點(diǎn) int DeleteByValue(LNode *L, int x) { LNode *p L; // p用于掃描前驅(qū) while (p-next ! NULL) { if (p-next-data x) { LNode *q p-next; p-next q-next; free(q); return 1; // 刪除成功 } p p-next; } return 0; // 沒(méi)有找到值為x的節(jié)點(diǎn) }按值刪除的掃描方式稍微有點(diǎn)特殊我讓p停在被刪節(jié)點(diǎn)的前驅(qū)位置判斷p-next-data是否等于x。這樣一旦找到不需要再額外找前驅(qū)直接操作p就能完成刪除。這個(gè)“讓指針停在當(dāng)前位置用p-next來(lái)操作”的寫(xiě)法在鏈表中非常實(shí)用需要熟到形成肌肉記憶。3.4 遍歷打印、求長(zhǎng)度、判空與修改基礎(chǔ)操作里的日常工具剩下幾個(gè)操作屬于“工具型操作”雖然代碼短但使用頻率極高我沒(méi)法不把它們收進(jìn)12個(gè)操作里。遍歷打印// 遍歷打印鏈表所有節(jié)點(diǎn)的值 void PrintList(LNode *L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }求鏈表長(zhǎng)度// 求鏈表長(zhǎng)度不含頭結(jié)點(diǎn) int Length(LNode *L) { int cnt 0; LNode *p L-next; while (p ! NULL) { cnt; p p-next; } return cnt; }判空與初始化// 初始化鏈表創(chuàng)建帶頭結(jié)點(diǎn)的空鏈表 LNode* InitList() { LNode *L (LNode*)malloc(sizeof(LNode)); if (L NULL) { return NULL; } L-next NULL; return L; } // 判斷鏈表是否為空 int IsEmpty(LNode *L) { return L-next NULL; }修改節(jié)點(diǎn)值// 修改第i個(gè)節(jié)點(diǎn)的值為新值 int ModifyAt(LNode *L, int i, int newVal) { LNode *p GetElem(L, i); if (p NULL) { return 0; } p-data newVal; return 1; }到這里12個(gè)操作全部覆蓋。你會(huì)發(fā)現(xiàn)這些代碼之間幾乎沒(méi)有“新東西”除了查找之外增刪改全是三兩行指針操作。這正是鏈表的特性邏輯簡(jiǎn)單但邊界極其容易出錯(cuò)。所以下面這個(gè)章節(jié)才是真正的考驗(yàn)場(chǎng)。4. 鏈表的進(jìn)階操作逆轉(zhuǎn)、排序、合并、去重、環(huán)檢測(cè)標(biāo)題雖然寫(xiě)的是“12個(gè)基礎(chǔ)操作”但只掌握12個(gè)基礎(chǔ)操作只能應(yīng)付教材上的練習(xí)題。面試和實(shí)際生產(chǎn)中鏈表的高頻考察點(diǎn)幾乎全部落在進(jìn)階操作上。這些操作也正好是檢驗(yàn)?zāi)闶欠裾嬲斫饬恕爸羔樦赶蜃兓钡淖詈迷嚱鹗?.1 鏈表逆轉(zhuǎn)迭代三指針?lè)ㄦ湵淼哪孓D(zhuǎn)說(shuō)白了就是把每個(gè)節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)。難點(diǎn)在于當(dāng)你把一個(gè)節(jié)點(diǎn)的next改掉之后原來(lái)的下一個(gè)節(jié)點(diǎn)就找不到了所以需要一個(gè)指針提前保存它。// 單鏈表原地逆轉(zhuǎn)帶頭結(jié)點(diǎn) void ReverseList(LNode *L) { LNode *prev NULL; // 前驅(qū)初始為空逆轉(zhuǎn)后原來(lái)的頭節(jié)點(diǎn)變尾指向NULL LNode *cur L-next; // 從第一個(gè)數(shù)據(jù)節(jié)點(diǎn)開(kāi)始 while (cur ! NULL) { LNode *next cur-next; // 先保存下一個(gè)節(jié)點(diǎn)防止丟失 cur-next prev; // 翻轉(zhuǎn)指針?lè)较?prev cur; // 前驅(qū)前移 cur next; // 當(dāng)前節(jié)點(diǎn)前移 } L-next prev; // 最后一個(gè)prev就是逆轉(zhuǎn)后的第一個(gè)節(jié)點(diǎn) }這個(gè)三指針?lè)ㄊ擎湵砟孓D(zhuǎn)的標(biāo)準(zhǔn)解法記憶時(shí)可以想象成“三個(gè)手指頭交替往前挪”。還有遞歸解法但在鏈表長(zhǎng)度較大時(shí)遞歸有棧溢出風(fēng)險(xiǎn)實(shí)戰(zhàn)中我基本都用三指針?lè)ā?.2 兩個(gè)有序鏈表的合并歸并思想從這入門(mén)合并兩個(gè)升序鏈表輸出還是升序這是歸并排序在鏈表上的一個(gè)前置操作。實(shí)現(xiàn)思路很簡(jiǎn)單兩個(gè)指針?lè)謩e指向兩個(gè)鏈表頭部誰(shuí)小誰(shuí)先接入新鏈表然后對(duì)應(yīng)指針后移。// 合并兩個(gè)升序鏈表返回新鏈表的頭指針不破壞原鏈表 LNode* MergeSortedList(LNode *L1, LNode *L2) { LNode *dummy (LNode*)malloc(sizeof(LNode)); // 新鏈表帶頭結(jié)點(diǎn) dummy-next NULL; LNode *tail dummy; // 尾指針接新節(jié)點(diǎn)用 LNode *p L1-next; LNode *q L2-next; while (p ! NULL q ! NULL) { if (p-data q-data) { tail-next p; p p-next; } else { tail-next q; q q-next; } tail tail-next; } // 把剩余部分整體接上 tail-next (p ! NULL) ? p : q; return dummy; }這里為什么允許直接接上剩余部分因?yàn)楹喜⒉僮髦皇侵匦陆M織節(jié)點(diǎn)之間的next關(guān)系每個(gè)節(jié)點(diǎn)本身的內(nèi)存沒(méi)變。剩余的那個(gè)鏈表片段天然有序直接掛上去即可。這個(gè)“整體接入”的思路比逐節(jié)點(diǎn)拷貝高效得多。4.3 鏈表排序冒泡與歸并的選擇如果想對(duì)一個(gè)無(wú)序鏈表排序最省事的是冒泡排序。雖然時(shí)間復(fù)雜度是O(n^2)但勝在代碼簡(jiǎn)單、空間復(fù)雜度為O(1)適合鏈表這種不支持隨機(jī)訪問(wèn)的結(jié)構(gòu)。// 鏈表冒泡排序只交換數(shù)據(jù)域不修改指針關(guān)系 void BubbleSortList(LNode *L) { if (L NULL || L-next NULL) { return; } int swapped; LNode *p; LNode *end NULL; // 指向已排序部分的尾部標(biāo)記 do { swapped 0; p L-next; while (p-next ! end) { if (p-data p-next-data) { // 交換兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)域 int tmp p-data; p-data p-next-data; p-next-data tmp; swapped 1; } p p-next; } end p; // 上一層循環(huán)結(jié)束時(shí)p指向無(wú)序區(qū)最后一個(gè)節(jié)點(diǎn)下一輪無(wú)序區(qū)縮短 } while (swapped); }注意我選擇的是“只交換數(shù)據(jù)不改指針”的方案。為什么不移動(dòng)節(jié)點(diǎn)本身因?yàn)橐苿?dòng)節(jié)點(diǎn)需要維護(hù)前驅(qū)關(guān)系涉及大量細(xì)節(jié)而數(shù)據(jù)交換在單鏈表里實(shí)現(xiàn)極其簡(jiǎn)單。如果數(shù)據(jù)域體積大比如每個(gè)節(jié)點(diǎn)存一個(gè)幾百字節(jié)的結(jié)構(gòu)體那交換數(shù)據(jù)的代價(jià)就很高不如改成指針移動(dòng)的排序。實(shí)際項(xiàng)目中根據(jù)場(chǎng)景取舍。追求更優(yōu)性能的話鏈表歸并排序是更好的選擇它可以做到O(n log n)且空間復(fù)雜度為O(log n)遞歸棧。這里不展開(kāi)完整的歸并排序代碼上面的MergeSortedList已經(jīng)是它的核心組件。4.4 無(wú)序鏈表去重哈希表與雙重循環(huán)無(wú)序鏈表去重最直觀的做法是雙重循環(huán)外層遍歷每一個(gè)節(jié)點(diǎn)內(nèi)層掃描它后面的所有節(jié)點(diǎn)刪除重復(fù)值。// 無(wú)序鏈表去重雙重循環(huán)版空間復(fù)雜度O(1) void RemoveDuplicate(LNode *L) { LNode *outer L-next; while (outer ! NULL) { LNode *prev outer; // prev是內(nèi)層掃描時(shí)“外層節(jié)點(diǎn)之后”部分的前驅(qū) LNode *inner outer-next; while (inner ! NULL) { if (inner-data outer-data) { // 刪除inner節(jié)點(diǎn) prev-next inner-next; free(inner); inner prev-next; // 注意刪除后inner要重新接到prev的后面 } else { prev inner; inner inner-next; } } outer outer-next; } }這個(gè)代碼的陷阱在于刪除節(jié)點(diǎn)后的指針移動(dòng)。刪除inner后原來(lái)的inner已經(jīng)被釋放不能再訪問(wèn)inner-next所以要把inner重新賦值為prev-next。這種“刪完當(dāng)前節(jié)點(diǎn)后指針怎么挪”的問(wèn)題在鏈表刪除類題目里反復(fù)出現(xiàn)值得單獨(dú)標(biāo)注。如果允許額外空間用一個(gè)哈希表記錄出現(xiàn)過(guò)的值可以讓時(shí)間復(fù)雜度從O(n^2)降到O(n)。工程上數(shù)據(jù)量大時(shí)優(yōu)先考慮哈希表方案但考場(chǎng)上如果明確限制空間雙重循環(huán)才是標(biāo)準(zhǔn)答案。4.5 快慢指針檢測(cè)環(huán)為什么慢指針一定能追上檢測(cè)鏈表是否有環(huán)經(jīng)典解法是快慢指針。快指針一次走兩步慢指針一次走一步。如果鏈表有環(huán)快指針一定會(huì)最終追上慢指針如果沒(méi)有環(huán)快指針先走到尾部NULL。// 檢測(cè)鏈表是否有環(huán)有環(huán)返回1無(wú)環(huán)返回0 int HasCycle(LNode *L) { LNode *fast L; LNode *slow L; while (fast ! NULL fast-next ! NULL) { fast fast-next-next; // 快指針走兩步 slow slow-next; // 慢指針走一步 if (fast slow) { return 1; // 相遇說(shuō)明有環(huán) } } return 0; // 快指針到達(dá)尾部說(shuō)明無(wú)環(huán) }為什么快指針一定能追上慢指針直觀解釋是進(jìn)入環(huán)之后快指針在和慢指針的速度差是每單位時(shí)間一個(gè)節(jié)點(diǎn)而環(huán)的長(zhǎng)度是有限的快指針相對(duì)慢指針每次縮短1個(gè)節(jié)點(diǎn)距離最多走一圈多就能追上。這不是什么玄學(xué)而是一個(gè)簡(jiǎn)單的追及問(wèn)題。如果進(jìn)一步要求找出環(huán)的入口節(jié)點(diǎn)可以這樣操作快慢相遇后把快指針重新指向頭結(jié)點(diǎn)然后把兩個(gè)指針都改成一次走一步再次相遇的位置就是環(huán)的入口。這個(gè)證明涉及一點(diǎn)數(shù)學(xué)推導(dǎo)感興趣的話可以自己證明一下結(jié)論非常優(yōu)雅。4.6 求鏈表的中間節(jié)點(diǎn)奇數(shù)偶數(shù)的統(tǒng)一解法求中間節(jié)點(diǎn)樸素做法是先遍歷一遍求長(zhǎng)度再走一半?？炻羔樋梢砸惶私鉀Q快指針到尾部時(shí)慢指針恰好在中點(diǎn)。// 求鏈表的中間節(jié)點(diǎn)偶數(shù)個(gè)節(jié)點(diǎn)時(shí)返回后一個(gè)中間節(jié)點(diǎn) LNode* FindMiddle(LNode *L) { LNode *fast L-next; LNode *slow L-next; while (fast ! NULL fast-next ! NULL) { fast fast-next-next; slow slow-next; } return slow; }這里有一個(gè)細(xì)節(jié)如果鏈表有偶數(shù)個(gè)節(jié)點(diǎn)例如4個(gè)快指針走兩步到達(dá)第3個(gè)節(jié)點(diǎn)慢指針在第2個(gè)再走兩步快指針變成NULL慢指針在第3個(gè)。也就是說(shuō)返回的是“后一個(gè)中間節(jié)點(diǎn)”。如果你需要偶數(shù)時(shí)返回前一個(gè)只需要把循環(huán)條件改成fast-next ! NULL fast-next-next ! NULL。這種細(xì)微的語(yǔ)義差異考試中經(jīng)常被拿來(lái)考自己實(shí)現(xiàn)時(shí)也要根據(jù)需求明確。5. 鏈表調(diào)試的真實(shí)踩坑記錄代碼能跑通是第一步能調(diào)試才是真本事。鏈表這種結(jié)構(gòu)一旦出問(wèn)題經(jīng)常是段錯(cuò)誤或者死循環(huán)肉眼很難看出來(lái)。這一節(jié)我把我自己實(shí)際寫(xiě)鏈表代碼時(shí)踩過(guò)的坑整理出來(lái)希望能幫你少走彎路。5.1 空指針與野指針段錯(cuò)誤的頭號(hào)元兇我早期寫(xiě)的鏈表代碼里段錯(cuò)誤絕大多數(shù)源于空指針或野指針訪問(wèn)。典型場(chǎng)景是查找函數(shù)返回NULL但調(diào)用方?jīng)]有判斷就直接訪問(wèn)p-data。// 錯(cuò)誤示范沒(méi)有判斷GetElem返回值 LNode *p GetElem(L, 5); p-data 100; // 如果第5個(gè)節(jié)點(diǎn)不存在這里直接段錯(cuò)誤預(yù)防措施是約定公共接口必須檢查返回值但這個(gè)約定光寫(xiě)在文檔里沒(méi)用要在代碼層面強(qiáng)約束。我的習(xí)慣是任何從函數(shù)返回的指針在解引用之前先問(wèn)一句“它為NULL時(shí)應(yīng)該怎么辦”。不能篤定“這個(gè)函數(shù)一定能返回非NULL”鏈表的節(jié)點(diǎn)本來(lái)就會(huì)被合法地刪空。5.2 指針移動(dòng)順序錯(cuò)了先接后斷的教訓(xùn)插入操作中如果先執(zhí)行了“前驅(qū)指向新節(jié)點(diǎn)”的操作原鏈表就斷了。這個(gè)過(guò)程我初學(xué)時(shí)的記憶方法就是一句口訣“先接后面的線再斷前面的線?！彼胁迦?、刪除、逆轉(zhuǎn)操作本質(zhì)上都在調(diào)整線頭的連接順序順序一錯(cuò)鏈表結(jié)構(gòu)就會(huì)被破壞。舉個(gè)具體的例子第i個(gè)位置插入時(shí)如果寫(xiě)反// 錯(cuò)誤示范順序反了 p-next s; // p原來(lái)指向的后繼節(jié)點(diǎn)被丟棄 s-next p-next; // 此時(shí)p-next已經(jīng)是s了s指向自己形成環(huán)這樣不僅丟掉了原鏈表的一部分還會(huì)讓新節(jié)點(diǎn)指向自己產(chǎn)生一個(gè)環(huán)。這種錯(cuò)誤的后果比段錯(cuò)誤還隱蔽因?yàn)槟憧赡懿粫?huì)立刻崩潰而是在遍歷時(shí)陷入死循環(huán)。5.3 邊界條件的檢測(cè)套路鏈表的邊界條件總結(jié)起來(lái)就三種空鏈表頭結(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)就是NULL。只含一個(gè)節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)操作完直接變空。操作位置在頭尾頭部插入刪除和尾部插入刪除是否還能正常走通。我調(diào)試鏈表代碼時(shí)有一個(gè)固定儀式找一個(gè)最簡(jiǎn)單的數(shù)據(jù)比如3個(gè)節(jié)點(diǎn)的鏈表手動(dòng)把插入、刪除、查找、逆轉(zhuǎn)全部走一遍。只要3個(gè)節(jié)點(diǎn)的場(chǎng)景全部正確90%的邊界問(wèn)題都能暴露出來(lái)。不要一上來(lái)就測(cè)幾千個(gè)節(jié)點(diǎn)的大數(shù)據(jù)調(diào)試成本太高問(wèn)題也不容易定位。5.4 調(diào)試鏈表的三板斧第一板斧是打印法。在每個(gè)關(guān)鍵步驟后打印鏈表內(nèi)容和節(jié)點(diǎn)地址觀察指針關(guān)系是否符合預(yù)期。具體可以打印出每個(gè)節(jié)點(diǎn)的值和指向下一個(gè)節(jié)點(diǎn)的地址。第二板斧是畫(huà)圖法。拿一張紙把鏈表節(jié)點(diǎn)畫(huà)出來(lái)模擬指針的移動(dòng)和修改。這個(gè)辦法看起來(lái)笨但對(duì)理解“先接后斷”的本質(zhì)特別有效。說(shuō)句實(shí)話我現(xiàn)在遇到復(fù)雜的鏈表問(wèn)題還是會(huì)用紙筆畫(huà)一畫(huà)。第三板斧是畫(huà)圖加斷言。C語(yǔ)言里可以加assert(p ! NULL)等斷言在調(diào)試版里強(qiáng)制檢查指針狀態(tài)。不過(guò)斷言只在調(diào)試期有效發(fā)布版最好關(guān)掉量產(chǎn)代碼里還是要靠手動(dòng)檢查返回值。最后分享一個(gè)我自己總結(jié)的調(diào)試思想寫(xiě)鏈表代碼不要圖快要一個(gè)函數(shù)一個(gè)函數(shù)地驗(yàn)證每寫(xiě)一個(gè)操作就用最標(biāo)準(zhǔn)的數(shù)據(jù)測(cè)一遍。很多初學(xué)者喜歡照著網(wǎng)上的代碼一次性抄完十幾個(gè)函數(shù)然后一起編譯一起跑結(jié)果報(bào)錯(cuò)之后完全不知道從哪里查。鏈表這種結(jié)構(gòu)它的調(diào)試必須“一次只動(dòng)一個(gè)地方”把每個(gè)操作的可靠性攢起來(lái)最后組合使用時(shí)才不會(huì)翻車(chē)。希望這篇拆解能幫你把數(shù)據(jù)結(jié)構(gòu)三要素落到實(shí)處把鏈表的每一個(gè)操作都變成自然而然的選擇而不是死記硬背的代碼片段。