鏈表高級操作與算法

鏈表是數據結構中的基礎，但也是面試和實際開發中的重點考察對象。今天我們將深入探討鏈表的高級操作和常見算法，讓你能夠輕松應對各種鏈表問題。

1.?鏈表翻轉 - 最經典的鏈表問題

鏈表翻轉是面試中的常見題目，也是理解鏈表指針操作的絕佳練習。

1.1 迭代方法實現

ListNode*?reverseList(ListNode*?head)?{ListNode*?prev?=?nullptr;ListNode*?curr?=?head;while?(curr?!=?nullptr)?{ListNode*?nextTemp?=?curr->next;?//?暫存下一個節點curr->next?=?prev;??????????????//?反轉指針prev?=?curr;????????????????????//?prev?前進curr?=?nextTemp;????????????????//?curr?前進}return?prev;?//?新的頭節點}

這種方法就像是在倒一疊書：你需要一本一本地翻轉，過程中需要記住當前的書、前一本書和下一本書的位置。時間復雜度為?O(n)，空間復雜度為 O(1)。

1.2?遞歸方法實現

ListNode*?reverseList(ListNode*?head)?{//?基本情況：空鏈表或只有一個節點if?(head?==?nullptr?||?head->next?==?nullptr)?{return?head;}//?遞歸反轉剩余部分ListNode*?newHead?=?reverseList(head->next);//?改變指針方向head->next->next?=?head;head->next?=?nullptr;return?newHead;}

遞歸方法更像是魔法，它先抵達鏈表尾部，然后在"歸"的過程中一個接一個地反轉指針。這就像是我們先走到隊列末尾，然后從末尾開始依次讓每個人面朝相反方向。

2. 檢測環形鏈表

在許多實際應用中，確定鏈表是否存在環（循環）非常重要，因為環會導致無限循環。

2.1 快慢指針法

bool?hasCycle(ListNode?*head)?{if?(!head?||?!head->next)?return?false;ListNode?*slow?=?head;ListNode?*fast?=?head;while?(fast?&&?fast->next)?{slow?=?slow->next;??????//?慢指針每次走一步fast?=?fast->next->next;?//?快指針每次走兩步if?(slow?==?fast)?return?true;?//?相遇則存在環}return?false;?//?如果fast到達NULL，則無環}

這就像操場上跑步的兩個人：一個跑得快，一個跑得慢。如果跑道是環形的，快的人最終會從后面追上慢的人；如果跑道是直線，快的人會先到終點。

2.2 找到環的入口點

ListNode?*detectCycle(ListNode?*head)?{if?(!head?||?!head->next)?return?nullptr;ListNode?*slow?=?head;ListNode?*fast?=?head;bool?hasCycle?=?false;//?檢測是否有環while?(fast?&&?fast->next)?{slow?=?slow->next;fast?=?fast->next->next;if?(slow?==?fast)?{hasCycle?=?true;break;}}if?(!hasCycle)?return?nullptr;//?找到環的入口點slow?=?head;while?(slow?!=?fast)?{slow?=?slow->next;fast?=?fast->next;}return?slow;?//?環的入口點}

這個算法使用了一個有趣的數學結論：當快慢指針相遇后，將慢指針重置到鏈表頭，然后兩個指針以相同的速度前進，它們會在環的入口處相遇。這就像兩個人在環形操場不同位置出發，經過一定圈數后在某個特定點相遇。

3. 找到鏈表的中間節點

找到鏈表的中間節點對于很多算法都是關鍵一步，比如排序或二分查找。


ListNode*?middleNode(ListNode*?head)?{ListNode*?slow?=?head;ListNode*?fast?=?head;while?(fast?&&?fast->next)?{slow?=?slow->next;fast?=?fast->next->next;}return?slow;}

這個技巧也利用了快慢指針。想象你和朋友沿著一條路走，朋友的速度是你的兩倍。當朋友到達終點時，你恰好在中間位置。如果鏈表長度為奇數，返回的是正中間的節點；如果為偶數，則返回的是中間偏右的節點。

4.?合并兩個有序鏈表

將兩個已排序的鏈表合并成一個新的排序鏈表是另一個常見問題。


ListNode*?mergeTwoLists(ListNode*?l1,?ListNode*?l2)?{//?創建啞節點作為合并鏈表的頭ListNode?dummy(0);ListNode*?tail?=?&dummy;while?(l1?&&?l2)?{if?(l1->val?<?l2->val)?{tail->next?=?l1;l1?=?l1->next;}?else?{tail->next?=?l2;l2?=?l2->next;}tail?=?tail->next;}//?連接剩余部分tail->next?=?l1???l1?:?l2;return?dummy.next;}

這就像合并兩隊排好隊的人，每次從兩隊的隊頭選擇較小的一個人加入新隊伍。

5. 判斷回文鏈表

回文是指從前向后和從后向前讀都相同的序列。判斷一個鏈表是否為回文鏈表是一個有趣的挑戰。

bool?isPalindrome(ListNode*?head)?{if?(!head?||?!head->next)?return?true;//?找到中間節點ListNode*?slow?=?head;ListNode*?fast?=?head;while?(fast->next?&&?fast->next->next)?{slow?=?slow->next;fast?=?fast->next->next;}//?反轉后半部分ListNode*?secondHalf?=?reverseList(slow->next);//?比較前半部分和反轉后的后半部分ListNode*?p1?=?head;ListNode*?p2?=?secondHalf;bool?result?=?true;while?(p2)?{if?(p1->val?!=?p2->val)?{result?=?false;break;}p1?=?p1->next;p2?=?p2->next;}//?恢復鏈表原狀（可選）slow->next?=?reverseList(secondHalf);return?result;}

這個算法的思路是：先找到鏈表的中點，然后反轉后半部分，最后從兩端向中間比較。這就像檢查一個單詞是否為回文：我們可以從兩端同時讀取并比較。

6. 刪除鏈表中的倒數第N個節點

這是一道考察鏈表遍歷技巧的經典題目。

ListNode*?removeNthFromEnd(ListNode*?head,?int?n)?{ListNode?dummy(0);dummy.next?=?head;ListNode*?first?=?&dummy;ListNode*?second?=?&dummy;//?第一個指針先前進?n+1?步for?(int?i?=?0;?i?<=?n;?i++)?{first?=?first->next;}//?兩個指針一起前進，直到第一個指針到達末尾while?(first)?{first?=?first->next;second?=?second->next;}//?刪除倒數第?n?個節點ListNode*?toDelete?=?second->next;second->next?=?second->next->next;delete?toDelete;return?dummy.next;}

這個技巧使用了兩個指針，兩者之間保持固定距離(n+1)。當第一個指針到達鏈表末尾時，第二個指針恰好指向倒數第?n+1 個節點，這樣我們就可以刪除倒數第 n?個節點了。這就像一列行進的士兵，當排頭到達終點時，排尾的位置也是確定的。

7. 劃分鏈表 -?奇偶節點分離

將鏈表按照奇偶位置劃分，先奇數位置的節點，再偶數位置的節點。

ListNode*?oddEvenList(ListNode*?head)?{if?(!head?||?!head->next)?return?head;ListNode*?odd?=?head;???????????//?奇數節點ListNode*?even?=?head->next;????//?偶數節點ListNode*?evenHead?=?even;??????//?保存偶數鏈表的頭while?(even?&&?even->next)?{odd->next?=?even->next;?????//?連接奇數節點odd?=?odd->next;even->next?=?odd->next;?????//?連接偶數節點even?=?even->next;}odd->next?=?evenHead;???????????//?連接奇偶兩個鏈表return?head;}

這個算法將鏈表分成兩部分：奇數位置節點和偶數位置節點，然后將偶數鏈表接在奇數鏈表后面。它就像是把隊伍中的人按單雙號分成兩隊，然后再把第二隊排在第一隊后面。

8. 復雜鏈表的復制

一個復雜鏈表，其中每個節點除了有一個 next 指針外，還有一個 random 指針，隨機指向鏈表中的任意節點或?NULL。復制這樣的鏈表是一個挑戰。

Node*?copyRandomList(Node*?head)?{if?(!head)?return?nullptr;//?第一步：在每個原始節點后創建一個新節點Node*?curr?=?head;while?(curr)?{Node*?copy?=?new?Node(curr->val);copy->next?=?curr->next;curr->next?=?copy;curr?=?copy->next;}//?第二步：處理random指針curr?=?head;while?(curr)?{if?(curr->random)?{curr->next->random?=?curr->random->next;}curr?=?curr->next->next;}//?第三步：分離兩個鏈表Node?dummy(0);Node*?newTail?=?&dummy;curr?=?head;while?(curr)?{newTail->next?=?curr->next;newTail?=?newTail->next;curr->next?=?curr->next->next;curr?=?curr->next;}return?dummy.next;}

這個巧妙的算法分三步：首先，在每個原始節點后創建其復制節點；然后，利用這種交替的結構設置random指針；最后，分離兩個鏈表。這就像是為一組人創建克隆體，每個克隆體站在原人后面，然后根據原有的社交關系建立克隆體之間的聯系，最后將克隆體組成新的隊伍。

9. 實際應用案例

9.1?LRU (最近最少使用) 緩存

LRU 緩存是一種常見的緩存淘汰策略，可以用鏈表實現。

class?LRUCache?{private:int?capacity;list<pair<int,?int>>?cache;?//?key-value對的鏈表unordered_map<int,?list<pair<int,?int>>::iterator>?map;?//?哈希表，快速找到key在鏈表中的位置public:LRUCache(int?capacity)?:?capacity(capacity)?{}int?get(int?key)?{auto?it?=?map.find(key);if?(it?==?map.end())?return?-1;//?將訪問的節點移到鏈表前端cache.splice(cache.begin(),?cache,?it->second);return?it->second->second;}void?put(int?key,?int?value)?{auto?it?=?map.find(key);if?(it?!=?map.end())?{//?更新已存在的keyit->second->second?=?value;cache.splice(cache.begin(),?cache,?it->second);return;}//?緩存已滿，刪除最久未使用的元素if?(cache.size()?==?capacity)?{int?oldKey?=?cache.back().first;cache.pop_back();map.erase(oldKey);}//?插入新元素到前端cache.emplace_front(key,?value);map[key]?=?cache.begin();}};

在這個實現中，我們使用雙向鏈表保存鍵值對，最近使用的在前，最久未使用的在后。哈希表用于O(1)時間內找到鏈表中的節點。這個例子展示了如何將鏈表和哈希表結合使用，實現高效的緩存機制。

9.2 多項式表示

鏈表可以用來表示多項式，每個節點代表一項，包含系數和指數。


struct?PolyNode?{int?coef;??//?系數int?exp;???//?指數PolyNode*?next;PolyNode(int?c,?int?e)?:?coef(c),?exp(e),?next(nullptr)?{}};//?兩個多項式相加PolyNode*?addPoly(PolyNode*?poly1,?PolyNode*?poly2)?{PolyNode?dummy(0,?0);PolyNode*?tail?=?&dummy;while?(poly1?&&?poly2)?{if?(poly1->exp?>?poly2->exp)?{tail->next?=?new?PolyNode(poly1->coef,?poly1->exp);poly1?=?poly1->next;}?else?if?(poly1->exp?<?poly2->exp)?{tail->next?=?new?PolyNode(poly2->coef,?poly2->exp);poly2?=?poly2->next;}?else?{int?sumCoef?=?poly1->coef?+?poly2->coef;if?(sumCoef?!=?0)?{tail->next?=?new?PolyNode(sumCoef,?poly1->exp);}poly1?=?poly1->next;poly2?=?poly2->next;}if?(tail->next)?tail?=?tail->next;}//?處理剩余項tail->next?=?poly1???poly1?:?poly2;return?dummy.next;}

這個例子展示了如何使用鏈表表示和操作多項式，是鏈表在代數計算中的一個實際應用。