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