链表高级操作与算法

链表是数据结构中的基础，但也是面试和实际开发中的重点考察对象。今天我们将深入探讨链表的高级操作和常见算法，让你能够轻松应对各种链表问题。

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;}

这个例子展示了如何使用链表表示和操作多项式，是链表在代数计算中的一个实际应用。