一.鏈表反轉(zhuǎn)讓每個節(jié)點的next指向它的前一個節(jié)點。原1-2-3-NULL反轉(zhuǎn)3-2-1-NULL1.初始化三個指針prev NULL; // 前驅(qū)指針指向當(dāng)前節(jié)點的前一個currenthead; // 當(dāng)前指針指向正在處理的節(jié)點nextNULL; // 后繼指針保存當(dāng)前節(jié)點的下一個2.循環(huán)處理每個節(jié)點循環(huán)條件current ! NULL //當(dāng)前指向的不為空1.保存下一個節(jié)點next current-next //保存當(dāng)前節(jié)點的下一個節(jié)點如果不保存修改 current-next 后后面的節(jié)點就丟失了next current-next; //保存節(jié)點2current-next prev; //1-NULLcurrent next; //繼續(xù)處理節(jié)點22.反轉(zhuǎn)指針方向current -nextprev; // 當(dāng)前節(jié)點指向前一個節(jié)點這是反轉(zhuǎn)的核心操作執(zhí)行前prev-NULLcurrent-1-2-3-NULL執(zhí)行后prev-NULL;current - 1 - NULL;↑ ( next指向了prev)現(xiàn)在節(jié)點1不再指向節(jié)點2而指向NULL3.移動前驅(qū)指針prev current; //prev移動到當(dāng)前節(jié)點執(zhí)行前:prev-NULL;current-1-NULL執(zhí)行prev current:prev-1-NULLcurrent-1-NULL4.移動當(dāng)前指針current next; //current 移到下一個節(jié)點執(zhí)行前prev-1-NULLcurrent-1-NULLnext-2-3-NULL執(zhí)行后prev-1-NULLcurrent-2-3-NULLnext -2-3-NULL3.返回新頭指針return prev; // prev 指向原鏈表的最后一個節(jié)點新鏈表的頭原鏈表最后一個節(jié)點 -prevcurrent-NULL返回prev,即新鏈表的頭節(jié)點迭代法struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* current head; struct ListNode* next NULL; while (current ! NULL) { next current-next; // 1. 保存下一個 current-next prev; // 2. 反轉(zhuǎn)指針 prev current; // 3. prev 前移 current next; // 4. current 前移 } return prev; }迭代法優(yōu)點時間復(fù)雜度最優(yōu)O(n)一次遍歷完成空間復(fù)雜度最優(yōu)O(1)只用了3個指針無棧溢出風(fēng)險不遞歸不會爆棧代碼簡潔7行核心代碼關(guān)鍵點必須保存next否則會丟失鏈表先反轉(zhuǎn)再移動順序不能錯返回prev新鏈表的頭節(jié)點時間復(fù)雜度時間O(n)空間O(1)二.頭節(jié)點帶頭節(jié)點有一個額外的dummy 節(jié)點哨兵節(jié)點不存儲實際數(shù)據(jù)不帶頭節(jié)點頭指針直接指向第一個數(shù)據(jù)節(jié)點帶頭節(jié)點的優(yōu)勢優(yōu)勢說明統(tǒng)一操作插入刪除不需要特判頭節(jié)點空鏈表處理鏈表永遠(yuǎn)不會為空dummy 永遠(yuǎn)存在代碼簡潔減少分支判斷邏輯統(tǒng)一更安全不會出現(xiàn)空指針異常三.鏈表插入1.尾插法帶尾指針最常用90% 的場景使用尾插法創(chuàng)建鏈表保持順序插入順序 鏈表順序簡單易用代碼直觀不易出錯O(1) 高效帶尾指針時插入操作是常數(shù)時間適用廣泛從數(shù)組創(chuàng)建、從文件讀取等都適用尾插法就是將新節(jié)點鏈接到當(dāng)前鏈表的最后一個節(jié)點之后并更新尾指針指向新節(jié)點。list-tail-next newNode; //舊尾節(jié)點指向新節(jié)點list-tailnewNode; //更新尾指針2.頭插法頭插法就是將新節(jié)點插入到鏈表的第一個有效節(jié)點之前并更新頭指針指向新節(jié)點。// 核心邏輯帶dummy newNode-next dummy-next; // 新節(jié)點指向舊的頭節(jié)點 dummy-next newNode; // dummy指向新節(jié)點 head newNode; // 更新head指針如果有維護(hù)head3.尾插法和頭插法區(qū)別對比頭插法尾插法插入位置鏈表頭部第一個有效節(jié)點之前鏈表尾部最后一個節(jié)點之后時間復(fù)雜度O(1)O(1)維護(hù)tail 尾指針數(shù)據(jù)順序逆序后插入的在前面保持順序先插入的在前面核心操作newNode-next head;head newNode;tail-next newNode;tail newNode;是否需遍歷不需要不需要維護(hù)tail指針適用場景棧LIFO、逆序構(gòu)建隊列FIFO、順序構(gòu)建緩存友好性較差訪問分散較好順序訪問4.中間插入查找鏈表的中間節(jié)點使用快慢指針方法。快指針每次移動兩步慢指針每次移動一步直到快指針到達(dá)鏈表末尾慢指針正好指向中間節(jié)點。創(chuàng)建新節(jié)點并將其插入到中間節(jié)點之后。更新新節(jié)點的next指向原中間節(jié)點的next然后將中間節(jié)點的next指向新節(jié)點。插入方式位置時間復(fù)雜度特點頭插法鏈表頭部O(1)插入順序逆序尾插法鏈表尾部O(1)/O(n)保持順序中間插入指定位置O(k)任意位置插入找到第 k-1 個節(jié)點前驅(qū)新節(jié)點指向原第 k 個節(jié)點前驅(qū)指向新節(jié)點。// 中間插入的核心操作 newNode-next prev-next; // ① 新節(jié)點指向原后繼 prev-next newNode; // ② 前驅(qū)指向新節(jié)點四.節(jié)點查找1.中間查找快慢指針慢指針每次走一步快指針每次走兩步。快指針到達(dá)末尾時慢指針在中間。如果有兩個中間節(jié)點返回第二個2.查找倒數(shù)第k個節(jié)點快指針先走 k 步然后快慢指針一起走。快指針到達(dá) NULL 時慢指針就在倒數(shù)第 k 個節(jié)點。五.刪除刪除第k個節(jié)點刪除鏈表中第 k 個節(jié)點需要找到第 k 個節(jié)點的前驅(qū)然后進(jìn)行刪除操作。六.合并