學做淘寶客網站,公司網站建設一般要多少錢,wordpress換頭像不顯示不出來,東臺市建設局網站在之前的鏈表學習中#xff0c;我們掌握了基本的增刪改查和雙指針技巧。今天#xff0c;我們要挑戰(zhàn)鏈表操作的“深水區(qū)”。 我們將通過兩個非常有代表性的題目#xff1a;K個一組翻轉鏈表 和 鏈表排序#xff0c;來探討如何在復雜的指針變換中保持邏輯清晰#xff0c;以及…在之前的鏈表學習中我們掌握了基本的增刪改查和雙指針技巧。今天我們要挑戰(zhàn)鏈表操作的“深水區(qū)”。我們將通過兩個非常有代表性的題目K個一組翻轉鏈表和鏈表排序來探討如何在復雜的指針變換中保持邏輯清晰以及如何將分治算法完美應用到鏈表結構中。這兩個問題不依賴額外的數據結構完全依靠對next指針的掌控是磨練代碼基本功的絕佳素材。一、 K個一組翻轉鏈表 (Reverse Nodes in k-Group)這個問題的難點不在于“翻轉”而在于“分組”和“縫合”。我們需要將鏈表切分成若干個長度為 k 的小段對每一段進行內部翻轉然后再把這些翻轉后的小段按照原來的順序重新連起來。1. 核心思路維護“守門員” p0如果只是單純翻轉一個鏈表我們只需要pre、cur、nxt三個指針就夠了。但在 K 個一組的場景下每一組翻轉后都需要跟上一組的尾巴和下一組的頭建立連接。因此我們需要一個關鍵指針p0。p0 的定義它始終指向當前待翻轉這一組的前一個節(jié)點。作用它就像一個“守門員”或“錨點”負責在這一組翻轉完畢后把斷開的鏈表重新縫合起來。2. 代碼解析代碼采用了先統計長度再循環(huán)處理的邏輯。C代碼實現class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // 1. 統計鏈表總長度 ListNode* cur head; int len 0; while (cur) { len 1; cur cur-next; } // 2. 初始化 dummy 節(jié)點和 p0 ListNode dummy(0, head); ListNode* p0 dummy; cur head; // cur 復位準備開始干活 ListNode* pre nullptr; // 3. 循環(huán)處理每一組條件是剩余長度 k while (len k) { len - k; // --- 內部翻轉邏輯 (標準的鏈表翻轉) --- for (int i 0; i k; i) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } // --- 縫合邏輯 (最難理解的部分) --- // 此時狀態(tài) // p0 - [原來的頭...原來的尾] - cur(下一組頭) // 翻轉后 // p0 依然指向 dummy/上一組尾 // pre 指向 [現在的頭(原來的尾)] // p0-next 指向 [現在的尾(原來的頭)] ListNode* nxt p0-next; // nxt 暫存的是這一組“原來的頭”現在它變成了尾巴 // 步驟 A: 將 p0 連接到 現在的頭 (pre) // 這一步修正了上一組和當前組的連接 p0-next-next cur; p0-next pre; // 步驟 B: 移動 p0 // p0 移動到這一組的尾巴 (也就是 nxt)為下一組做好準備 p0 nxt; } return dummy.next; } };3. 難點拆解縫合過程代碼中最晦澀的這四行C代碼實現ListNode* nxt p0-next; p0-next-next cur; p0-next pre; p0 nxt;圖解我們可以這樣理解鎖定舊頭nxt p0-next。因為翻轉前p0-next指向這一組的第一個元素例如 1翻轉后它變成了這組的最后一個元素。連接下組p0-next-next cur。也就是讓 1 指向下一組的開頭例如 4。等價于1-next 4。連接上組p0-next pre。讓p0指向這一組翻轉后的新頭例如 3。等價于dummy-next 3。移動 p0p0 nxt。當前組處理完了p0跳到 1 的位置蹲守在 4 的前面準備處理下一組。4. 復雜度分析時間復雜度O(N)。我們需要先遍歷一次求長度然后再次遍歷翻轉。每個節(jié)點最多被訪問兩次所以是線性的?？臻g復雜度O(1)。我們可以看到除了幾個指針變量外沒有使用額外的數組或?？臻g是原地算法。二、 鏈表排序 (Sort List)在數組排序中快速排序通常是首選。但在鏈表中由于無法隨機訪問無法 O(1) 獲取中間元素快速排序的性能會大打折扣。因此歸并排序 (Merge Sort)是鏈表排序的最佳拍檔。1. 核心思路分治法 (Divide and Conquer)歸并排序的核心就三步找中點 (Cut)把鏈表從中間切斷分成左右兩半。遞歸 (Sort)對左右兩半分別進行排序。合并 (Merge)將兩個有序的鏈表合并成一個有序鏈表。2. 代碼解析C代碼實現class Solution { // 輔助函數1找中點并斷開鏈表 ListNode* getMidNode(ListNode* head) { ListNode* slow head; ListNode* fast head; ListNode* pre nullptr; // 用于記錄中點的前一個節(jié)點方便斷鏈 // 快慢指針找中點 while(fast fast-next) { pre slow; slow slow-next; fast fast-next-next; } // 關鍵操作斷開鏈表 // 如果不斷開這就不是分治而是死循環(huán) if (pre ! nullptr) { pre-next nullptr; } return slow; // slow 就是后半段的頭 } // 輔助函數2合并兩個有序鏈表 (雙指針拉拉鏈) ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } // 接上剩余的部分 cur-next l1 ? l1 : l2; return dummy.next; } public: ListNode* sortList(ListNode* head) { // 遞歸終止條件鏈表為空或只有一個節(jié)點 if (head nullptr || head-next nullptr) { return head; } // 1. 分找到中點head 是前半段head2 是后半段 ListNode* head2 getMidNode(head); // 2. 治遞歸排序左右兩半 head sortList(head); head2 sortList(head2); // 3. 合合并兩個有序鏈表 return merge(head, head2); } };3. 細節(jié)剖析找中點技巧使用快慢指針Slow/Fast Pointers?？熘羔樢淮巫邇刹铰羔樢淮巫咭徊?。當快指針走到頭時慢指針剛好在中間。斷鏈操作在getMidNode中我們需要維護一個pre指針指向慢指針的前一個節(jié)點。找到中點后執(zhí)行pre-next nullptr。這一步至關重要它將大鏈表物理上拆分成了兩個獨立的鏈表否則遞歸無法收斂。Base Caseif (head nullptr || head-next nullptr)。這是遞歸的出口當鏈表被拆解成單個節(jié)點時單個節(jié)點天然就是有序的。4. 復雜度分析時間復雜度O(N log N)。分治的過程就像一棵二叉樹層數為 log N。每一層合并操作需要遍歷所有節(jié)點耗時 N。總耗時為 N * log N。空間復雜度O(log N)。雖然我們沒有申請數組但是遞歸調用需要使用系統棧。棧的深度取決于遞歸的層數也就是鏈表切分的次數即 log N。注如果采用自底向上的迭代式歸并排序空間復雜度可以優(yōu)化到 O(1)但代碼可讀性會變差遞歸寫法通常是標準解法。三、 總結這兩道題目代表了鏈表操作的兩個高峰K個一組翻轉考驗的是局部操作與整體連接的協調能力。通過引入p0指針我們將復雜的切分和重連問題轉化為了標準的“反轉縫合”流程。鏈表排序考驗的是分治思想在鏈表上的落地。通過快慢指針解決切分問題通過遞歸解決排序問題這是解決復雜鏈表問題的通用模板。掌握了這兩個“大殺器”再回頭看普通的鏈表反轉或合并就會覺得游刃有余了。