“初始化鏈表要二級指針頭插法只要一級指針”這個(gè)問題我在好幾個(gè)場合都遇到過課上被同學(xué)截住問、面試時(shí)被主考官拋出來、論壇上被新手反復(fù)拿來討論。能把這個(gè)問題真正講清楚的人不算多很多回答只丟一句“因?yàn)槌跏蓟闹羔槺旧怼钡珵槭裁锤闹羔槺旧砭偷枚夘^插法不是也把鏈表頭換掉了嗎這里頭藏著C語言函數(shù)參數(shù)傳遞最基本、也最容易被忽視的那套邏輯。這篇文我就從內(nèi)存模型講到代碼寫法把這兩個(gè)操作掰開揉碎再順帶把常見的坑和調(diào)試手段都給你理一遍。適合正在學(xué)單鏈表的初學(xué)者也適合準(zhǔn)備面試、想把這題答出深度的人。結(jié)論先放這兒判斷一個(gè)函數(shù)到底該用一級指針還是二級指針不看你操作的是不是鏈表頭而看你有沒有在函數(shù)內(nèi)部修改“調(diào)用者手里的那個(gè)指針變量本身”。下面逐步展開。1. 先把基礎(chǔ)錘實(shí)指針變量、內(nèi)存地址和“改誰”的問題很多初學(xué)者一看到“二級指針”四個(gè)字就開始發(fā)怵其實(shí)它沒那么玄前提是把一級指針看明白。1.1 指針變量本身也是變量它有自己的地址指針是什么官方說法是“存放地址的變量”。很多人只記住了后半句“存放地址”卻忽略了它首先是“變量”。變量就有三要素類型、值、地址。一個(gè)Node *head的變量類型是Node *值是一個(gè)地址也就是某個(gè)節(jié)點(diǎn)的內(nèi)存地址或者NULL它自己也有一個(gè)內(nèi)存地址也就是head。這里特別容易混淆的是“head 的值”和“head 的地址”。head的值指向節(jié)點(diǎn)head是指向 head 變量本身的地址。打個(gè)比方你把一串鑰匙放在門口的抽屜里抽屜上貼著標(biāo)簽“head”。head這個(gè)變量就是抽屜head就是“儲藏室第幾排第幾個(gè)抽屜”的定位信息。你平時(shí)用head-data是在看抽屜里那把鑰匙指向的房間里的擺設(shè)但如果你想換掉抽屜里那把鑰匙你只有先知道抽屜在哪才能打開抽屜把鑰匙換走。1.2 “二級指針”到底長什么樣二級指針就是指針的指針。定義起來很簡單Node *head NULL; Node **pp head;這里pp的類型是Node **它存放的是head這個(gè)指針變量的地址。用*pp就能拿到head也就是Node *類型的指針再用**pp才能拿到頭節(jié)點(diǎn)本身。我習(xí)慣這樣理解如果說一級指針是“記下某個(gè)房間的門牌號”那二級指針就是“記下寫著門牌號那張紙條放在了哪本通訊錄的第幾頁”。你不光能看書上寫的門牌號還能把那一頁撕掉換一張新紙條上去。1.3 函數(shù)參數(shù)傳遞的本質(zhì)形參是實(shí)參的復(fù)印件C語言函數(shù)傳參是值傳遞。調(diào)用f(a)時(shí)函數(shù)里的形參拿到的是a的副本不是a本身。函數(shù)里無論怎么修改形參外面的a都紋絲不動。這是理解整個(gè)問題的根基。所以想讓函數(shù)修改外部變量幾乎沒有捷徑必須把外部變量的地址傳進(jìn)去。外部變量如果是普通int就傳int *外部變量如果本身是一個(gè)指針那想修改它就得傳“指針的地址”也就是二級指針。這不是鏈表獨(dú)有的規(guī)矩是所有 C 函數(shù)通用的規(guī)則。2. 初始化鏈表為什么必須用二級指針初始化鏈表最常見的需求就是把鏈表頭指針置為空NULL表示“這是空鏈表”。初學(xué)者很容易寫出下面這種看似沒毛病、實(shí)則完全不對的代碼。2.1 常見錯(cuò)誤用一級指針初始化void initList(Node *list) { list NULL; }調(diào)用int main(void) { Node *head NULL; initList(head); return 0; }結(jié)果是什么head仍然是原來的值。因?yàn)楹瘮?shù)里的list只是head的一份拷貝list NULL只把這份拷貝改成了空而外面的head和這個(gè)拷貝沒有任何聯(lián)系。等函數(shù)返回list消失一切恢復(fù)原狀。你可以打印地址驗(yàn)證void initList(Node *list) { printf(函數(shù)內(nèi) list 變量自己的地址: %p\n, list); printf(函數(shù)外傳入 head 的值: %p\n, list); list NULL; }再看外面Node *head (Node*)0x1234; initList(head); printf(外面 head 的值: %p\n, head); // 還是 0x1234函數(shù)修改的只是一個(gè)副本這個(gè)副本和外面的head變量本體沒有任何關(guān)系。犯這個(gè)錯(cuò)的根源就是把“指針變量”和“指針指向的內(nèi)容”搞混了。2.2 正確寫法用二級指針初始化要讓函數(shù)修改外面的head就得傳head也就是Node **void initList(Node **list) { *list NULL; }調(diào)用int main(void) { Node *head NULL; initList(head); return 0; }這時(shí)候函數(shù)里的list是head的地址*list訪問的正是head變量本身。*list NULL就是把外面的head改為NULL。理解到這一步初始化為什么用二級指針其實(shí)已經(jīng)清楚了因?yàn)槌跏蓟薷牡氖恰罢{(diào)用者作用域里的那個(gè)指針變量”而修改一個(gè)指針變量必須拿到它的地址也就是二級指針。提示初始化鏈表不只是“置空”這一種寫法。有的實(shí)現(xiàn)會帶頭節(jié)點(diǎn)哨兵節(jié)點(diǎn)需要 malloc 一個(gè)節(jié)點(diǎn)那同樣要改外面的head所以依然要二級指針。核心沒變誰要修改head這個(gè)變量的值誰就得拿二級指針。2.3 為什么這道題特別愛考這道題能成為經(jīng)典面試題不是因?yàn)樗y而是它能把一整套關(guān)鍵概念串起來值傳遞、指針變量、地址、間接訪問。面試官問這個(gè)問題表面上是問鏈表初始化實(shí)際上在看你能不能分清“傳地址”和“傳指針的值”的區(qū)別。有人會問那我不用二級指針讓初始化函數(shù)返回新頭不行嗎Node *initList(void) { return NULL; }調(diào)用處head initList();也可以。但這帶來一個(gè)隱患調(diào)用者必須記得接收返回值。如果哪次忘記賦值head就沒被初始化后續(xù)操作就是野指針。接口設(shè)計(jì)上“修改指針本身”的操作用二級指針往往更直白因?yàn)楹灻锞蛯懼拔乙哪恪?。另外如果初始化不只是置空還要分配哨兵節(jié)點(diǎn)、設(shè)置長度字段返回值風(fēng)格的代碼就會變成head createList();你得先創(chuàng)建后再傳回邏輯上沒問題但實(shí)際項(xiàng)目里更常見的還是把操作封裝成void initList(List **list)因?yàn)槌跏蓟瘮?shù)要做的事情更復(fù)雜返回一個(gè)指針表達(dá)不了多重狀態(tài)。3. 頭插法為什么一級指針就夠了它修改的到底是什么再來看頭插法。不少人的困惑在這頭插法不是也在“換頭”嗎換頭不也要改 head 指針嗎為什么一級指針就夠了3.1 先明確一個(gè)容易忽略的事實(shí)頭插法的“頭”指的是鏈表第一個(gè)節(jié)點(diǎn)不是 head 變量。標(biāo)準(zhǔn)頭插法做的事情拆開看是兩步新節(jié)點(diǎn)的next指向舊的第一個(gè)節(jié)點(diǎn)讓head指向新節(jié)點(diǎn)。第二步確實(shí)是在改變頭指針的指向。但是注意實(shí)現(xiàn)方式。大多數(shù)教材給的頭插法函數(shù)是Node *insertHead(Node *head, int data) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data data; newNode-next head; return newNode; }調(diào)用處這樣用head insertHead(head, data);函數(shù)里的head是實(shí)參的拷貝它只被讀取、沒有要求被修改。真正讓外部head指向新節(jié)點(diǎn)的是調(diào)用處那行head ...這個(gè)賦值發(fā)生在 main 的作用域里不在函數(shù)內(nèi)部。所以這里一級指針就夠用了因?yàn)閷nsertHead而言它需要的只是“舊頭節(jié)點(diǎn)的地址”這個(gè)信息用來給newNode-next賦值。它不需要去修改調(diào)用者持有的head變量因?yàn)檎{(diào)用者自己會用返回值把 head 更新掉。3.2 “一級指針就夠了”不等于“只能用一級指針”如果你希望頭插法函數(shù)內(nèi)部把外部 head 直接改掉那依然要用二級指針void insertHead(Node **head, int data) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data data; newNode-next *head; *head newNode; }調(diào)用處變成insertHead(head, data);這種寫法更“原子”不用靠返回值調(diào)用者也少一個(gè)忘記賦值的風(fēng)險(xiǎn)。所以準(zhǔn)確的說法是標(biāo)準(zhǔn)頭插法接口通常設(shè)計(jì)成一級指針加返回值因?yàn)楹瘮?shù)本意是“基于舊頭構(gòu)造新頭并返回”而不是“原地改寫舊頭變量”。如果你非要原地改二級指針必不可少。兩種風(fēng)格對比設(shè)計(jì)函數(shù)簽名調(diào)用方式修改調(diào)用者h(yuǎn)ead的方式風(fēng)險(xiǎn)點(diǎn)返回新頭Node *insertHead(Node*, int)head insertHead(head, x)在調(diào)用處用返回值賦值忘記接收返回值會丟頭二級指針void insertHead(Node**, int)insertHead(head, x)函數(shù)內(nèi)部*head newNode參數(shù)寫法稍顯別扭實(shí)際工程里返回新頭的風(fēng)格用得更廣因?yàn)榭勺x性好、鏈?zhǔn)秸{(diào)用方便但遇到需要批量插入、或者要同時(shí)做多個(gè)判斷時(shí)二級指針能少寫不少累贅的賦值語句。兩者沒有絕對的優(yōu)劣選哪一種取決于團(tuán)隊(duì)習(xí)慣和維護(hù)成本。3.3 那“在表頭插入節(jié)點(diǎn)”到底改了哪些內(nèi)存這是很多人的理解盲區(qū)。你畫鏈表示意圖的時(shí)候可能會畫出“head 箭頭指向第一個(gè)節(jié)點(diǎn)”頭插之后“head 箭頭指向新節(jié)點(diǎn)”。這個(gè)圖會讓人誤以為函數(shù)內(nèi)部必須改 head。實(shí)際上插入動作發(fā)生在節(jié)點(diǎn)層面新節(jié)點(diǎn)的next字段被寫入舊頭的地址然后head變量的值被換成新節(jié)點(diǎn)地址。前者是修改節(jié)點(diǎn)對象的內(nèi)容只需要知道舊頭地址就能做后者是修改變量head的值這件事要么在調(diào)用處用做要么在函數(shù)內(nèi)部通過二級指針做。所以回到標(biāo)題的說法“頭插法只要一級指針”是這套約定俗成接口下的結(jié)論。如果考題真的改成“寫一個(gè)函數(shù)在鏈表頭部插入節(jié)點(diǎn)要求在函數(shù)內(nèi)部直接完成不借助返回值”那答案就又變成二級指針了。面試時(shí)把這個(gè)邊界說清楚往往比死記結(jié)論更容易加分。3.4 關(guān)于虛擬頭結(jié)點(diǎn)和結(jié)構(gòu)體封裝的特殊情況有些鏈表實(shí)現(xiàn)會引入虛擬頭結(jié)點(diǎn)dummy head讓鏈表永遠(yuǎn)有一個(gè)“占位”的節(jié)點(diǎn)真正的數(shù)據(jù)節(jié)點(diǎn)從dummy-next開始。這種設(shè)計(jì)下頭插法只需要修改dummy-next而 dummy 本身不變。如果你用結(jié)構(gòu)體封裝typedef struct { Node *head; int length; } LinkedList; void initList(LinkedList *list) { list-head NULL; list-length 0; }這就是典型的“通過一級指針修改結(jié)構(gòu)體成員”。這里的list指向調(diào)用者創(chuàng)建的LinkedList變量函數(shù)修改的是這個(gè)變量的head成員而不是修改list指針本身所以一級指針足夠。這類寫法在工程里很常見因?yàn)樗焰湵淼男畔⒓泄芾砹恕?. 常見誤區(qū)與實(shí)戰(zhàn)排查技巧看到這理論層面應(yīng)該通了。但真正自己寫代碼的時(shí)候還會踩到各種奇奇怪怪的坑。我把這幾年見到的錯(cuò)誤歸類了一下基本就這幾個(gè)。4.1 誤區(qū)一分不清“傳地址”和“傳指針的值”initList(head)和initList(head)的區(qū)別看著就一個(gè)實(shí)際上天差地別。前者傳的是“head 指向的地址”后者傳的是“head 這個(gè)變量本身的地址”。很多同學(xué)在紙上畫圖時(shí)明白一敲代碼就按自己的想法亂傳。解決辦法很簡單寫函數(shù)簽名前先問自己一句我在函數(shù)里修改的是“節(jié)點(diǎn)”還是“指針變量本身”。改節(jié)點(diǎn)傳一級改指針變量本身傳二級。4.2 誤區(qū)二拿到二級指針后寫錯(cuò)訪問方式正確用法是void initList(Node **list) { (*list)-data 0; // 修改頭節(jié)點(diǎn)內(nèi)容 *list NULL; // 修改 head 指針本身 }有些人拿到二級指針后會用list-data這里list本身是Node **list-data根本編譯不過。真想訪問頭節(jié)點(diǎn)得(*list)-data。還有一個(gè)常見的壞習(xí)慣是把二級指針和野指針混在一起Node **list;不初始化就直接寫給*list這極其危險(xiǎn)因?yàn)槟悴恢纋ist的地址里原本是什么野值。提示二級指針本身也必須指向合法的地址。Node **list指向誰它指向調(diào)用者的 head 變量。如果你沒傳head而是傳了一個(gè)未初始化的Node **那*list就是在瞎寫內(nèi)存崩潰只是時(shí)間問題。4.3 誤區(qū)三覺得二級指針能處理一切濫用它不是所有鏈表操作都要二級。比如修改某個(gè)節(jié)點(diǎn)的data傳入Node *就行。比如刪除“鏈表中某個(gè)給定節(jié)點(diǎn)之后的一個(gè)節(jié)點(diǎn)”你只需要前驅(qū)節(jié)點(diǎn)的一級指針。二級指針主要用于“需要修改某個(gè)指針變量本身”的場景。如果把所有操作都升級成二級指針代碼會變得很繞別人讀起來問號滿臉。反過來也有人因?yàn)榕露壷羔樣灿梅祷刂道@開。風(fēng)險(xiǎn)是調(diào)用處必須連續(xù)寫head xxx(head, ...)一旦漏掉一次head 就停留在錯(cuò)誤狀態(tài)排查起來很痛苦。真正的解法不是“永遠(yuǎn)避開二級指針”而是“搞清楚該用的時(shí)候別躲不該用的時(shí)候別顯擺”。4.4 調(diào)試實(shí)招用 printf 和 gdb 驗(yàn)證指針變化遇到指針相關(guān)的問題最好的朋友是打印。初始化函數(shù)前后可以這樣打void initList(Node **list) { printf(函數(shù)內(nèi) list 的地址: %p\n, list); printf(函數(shù)內(nèi) list 的值head的當(dāng)前值: %p\n, *list); *list NULL; printf(置空后 *list 的值: %p\n, *list); }調(diào)用處Node *head NULL; printf(調(diào)用前 head 的地址: %p\n, head); initList(head); printf(調(diào)用后 head 的值: %p\n, head);看到head和函數(shù)內(nèi)的list一致就說明你確實(shí)傳了 head 的地址看到*list變化、head 跟著變化就說明函數(shù)確實(shí)在修改外部變量。用 gdb 也可以在函數(shù)內(nèi)print list、print *list再回到外層print head一清二楚。4.5 操作類型與指針層級速查表操作修改的目標(biāo)推薦簽名原因置空頭指針head 變量本身void init(Node **)要修改外部 head創(chuàng)建頭結(jié)點(diǎn)head 變量本身void create(Node **)或Node *create()返回式要手動賦值頭插法(標(biāo)準(zhǔn)版)新節(jié)點(diǎn)的 next 和調(diào)用處的 headNode *insert(Node*, int)函數(shù)內(nèi)不修改外部 head頭插法(原地版)head 變量本身void insert(Node **, int)函數(shù)內(nèi)直接改 head刪除第一個(gè)節(jié)點(diǎn)head 變量本身void popFront(Node **)或Node *popFront(Node*)刪除后頭要移位刪除中間節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)的 next 成員void removeAfter(Node*)修改的是節(jié)點(diǎn)成員不是指針變量修改節(jié)點(diǎn)數(shù)據(jù)節(jié)點(diǎn)對象的數(shù)據(jù)成員void setData(Node*, int)修改的是節(jié)點(diǎn)本身這張表不是讓你背是讓你找規(guī)律。凡是“修改目標(biāo)”一欄寫著“head 變量本身”的都需要二級指針或返回值寫著“節(jié)點(diǎn)成員”的一級指針就夠了。5. 純代碼演示完整單鏈表初始化加頭插空談太多容易飄我直接貼一段可以跑的單鏈表代碼配合注釋看重點(diǎn)就在初始化和頭插的指針使用上。5.1 二級指針初始化加一級指針頭插#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 初始化使用二級指針因?yàn)橐薷恼{(diào)用者的 head 本身 void initList(Node **list) { *list NULL; } // 頭插法使用一級指針加返回值 Node *insertHead(Node *head, int data) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { fprintf(stderr, malloc failed\n); exit(1); } newNode-data data; newNode-next head; return newNode; } // 打印鏈表 void printList(Node *head) { Node *cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); } int main(void) { Node *head NULL; initList(head); int values[] {10, 20, 30}; for (int i 0; i 3; i) { head insertHead(head, values[i]); } printList(head); return 0; }輸出30 - 20 - 10 - NULL因?yàn)槊看晤^插數(shù)據(jù)就是倒著輸出這是頭插法本身的特性。5.2 關(guān)鍵行解讀initList(head)中的head是Node **類型函數(shù)內(nèi)*list NULL做的是“把 head 變量置空”。在 main 里head聲明為Node *未初始化之前是野值所以初始化這一步非常重要不初始化就插入insertHead里newNode-next head會把野值寫進(jìn)新節(jié)點(diǎn)的 next鏈表整個(gè)就是壞的。head insertHead(head, values[i])這行是兩種傳遞方式連接的關(guān)鍵insertHead 函數(shù)的形參Node *head是外部老值的拷貝函數(shù)返回的是一個(gè)新地址等號左邊的head是 main 里的變量這行語句在 main 作用域更新了 head。一級指針在這里能成立是因?yàn)椤案?head 變量”的動作移到了函數(shù)外。5.3 如果頭插也用二級指針寫法長這樣void insertHeadVersion2(Node **list, int data) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { fprintf(stderr, malloc failed\n); exit(1); } newNode-data data; newNode-next *list; // 先連上舊頭 *list newNode; // 再把頭更新為新節(jié)點(diǎn) }調(diào)用處insertHeadVersion2(head, values[i]);這樣寫newNode 的 next 來自當(dāng)前的*list然后更新*list為 newNode。如果你忘了*list newNode新節(jié)點(diǎn)就會每次插入后都消失在鏈表外鏈表永遠(yuǎn)只有最后一個(gè)插入的節(jié)點(diǎn)。這種 bug 很隱蔽打印鏈表時(shí)不是崩潰就是少數(shù)據(jù)排查時(shí)先檢查有沒有“更新指針本身”。兩種版本運(yùn)行結(jié)果完全一樣。區(qū)別在于“責(zé)任落在誰身上”返回新版需要調(diào)用者完成head ...的賦值二級指針版把這一步留在函數(shù)內(nèi)部。理解這兩個(gè)版本你才算真正掌握了這題的靈魂。6. 這個(gè)知識點(diǎn)往后還能怎么用搞懂初始化鏈表這題收益不只是會寫鏈表。后面好幾類代碼都會用到同一個(gè)思維模型要不要改指針變量本身。我把常見場景列出來你會更有體感。6.1 刪除鏈表節(jié)點(diǎn)時(shí)的“帶頭刪除”刪除第一個(gè)節(jié)點(diǎn)和頭插同理如果函數(shù)要在內(nèi)部把 head 指向下一個(gè)節(jié)點(diǎn)就需要二級指針或返回值。很多實(shí)現(xiàn)長這樣void deleteHead(Node **list) { if (*list NULL) { return; } Node *tmp *list; *list (*list)-next; free(tmp); }調(diào)用deleteHead(head)直接改掉了外部 head不需要返回值。如果你用返回值風(fēng)格就得寫head deleteHead(head);忘了賦值刪除后 head 指向的舊節(jié)點(diǎn)已經(jīng) free再訪問就是懸空指針。這是我實(shí)際調(diào)試中見過最多的崩潰來源之一。6.2 二叉樹遞歸插入時(shí)修改根節(jié)點(diǎn)在建樹或插入節(jié)點(diǎn)時(shí)遞歸函數(shù)往往要修改根指針。比如二叉搜索樹插入用二級指針可以簡化代碼void insert(TreeNode **root, int val) { if (*root NULL) { *root createNode(val); return; } if (val (*root)-data) { insert((*root)-left, val); } else { insert((*root)-right, val); } }遞歸層次很深時(shí)如果不用二級指針你得寫*root insert(*root, val)并且要處理好返回值代碼會更繞。二級指針在遞歸里很常用本質(zhì)還是“要修改指針變量的值”。6.3 動態(tài)數(shù)組擴(kuò)容、釋放后置 NULL 等場景動態(tài)數(shù)組 realloc 之后原來的指針地址可能變化你需要把新的地址寫回外部指針變量這也是“修改指針變量本身”的場景。還有釋放完內(nèi)存后把指針置 NULL防止懸空void destroy(Node **head) { // 先釋放所有節(jié)點(diǎn)最后把頭指針置空 Node *cur *head; while (cur) { Node *next cur-next; free(cur); cur next; } *head NULL; }如果這里只傳Node *head函數(shù)結(jié)束后外部 head 仍指向已釋放的內(nèi)存后續(xù) if (head ! NULL) 檢查等于白做。把這些場景歸在一起看你就明白“二級指針”不是鏈表題專用的奇技淫巧而是C語言“函數(shù)修改外部變量”體系里的一環(huán)。我個(gè)人在帶新人時(shí)有個(gè)習(xí)慣遇到指針問題先拿筆畫兩層內(nèi)存出來畫清楚誰指向誰、誰要改誰再決定傳什么參數(shù)。畫完基本不會錯(cuò)。有時(shí)候代碼寫出來跑不過不是語法問題就是傳參那一刻想的和函數(shù)里做的不一致。初始化鏈表這道題最好的意義就是讓你在早期就養(yǎng)成這個(gè)習(xí)慣后面寫復(fù)雜數(shù)據(jù)結(jié)構(gòu)時(shí)能少踩很多坑。