【数据结构】链表核心算法实战：从基础操作到高阶应用
1. 链表基础操作从增删改查说起链表作为最基础的数据结构之一本质上是一系列节点的集合每个节点包含数据和指向下一个节点的指针。和数组不同链表在内存中不是连续存储的这使得它在插入和删除操作上具有天然优势。记得我第一次用链表实现学生管理系统时发现插入新同学信息只需要修改几个指针完全不需要像数组那样移动大量元素。先来看最基础的链表结构定义以C语言为例typedef struct ListNode { int val; struct ListNode *next; } ListNode;遍历链表就像数珍珠项链上的珠子void traverse(ListNode *head) { ListNode *cur head; while (cur ! NULL) { printf(%d , cur-val); cur cur-next; } }插入节点的关键是注意指针修改顺序。比如在节点A后插入新节点B先把B的next指向A原来的下一个节点再把A的next指向Bvoid insertAfter(ListNode *prev, int val) { ListNode *newNode (ListNode*)malloc(sizeof(ListNode)); newNode-val val; newNode-next prev-next; prev-next newNode; }删除节点时最容易犯的错误是忘记释放内存。删除节点A的后继节点void deleteAfter(ListNode *prev) { ListNode *toDelete prev-next; prev-next toDelete-next; free(toDelete); // 这个free千万别漏 }提示链表操作最怕指针丢失。建议在修改指针前先用临时变量保存关键节点地址就像把重要文件备份一样。2. 双指针技巧解决链表问题的瑞士军刀双指针是我最爱的链表解题工具就像同时用两根手指在链表上跳舞。最常见的快慢指针组合一个指针跑得快一个跑得慢能解决很多看似复杂的问题。经典例题链表中点查找ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }快指针每次走两步慢指针每次走一步当快指针走到尽头时慢指针正好在中点。这个算法只需要一次遍历时间复杂度O(n)空间复杂度O(1)。另一个妙用判断链表是否有环bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }如果链表有环快指针最终会追上慢指针就像跑道上快跑者套圈慢跑者一样。进阶应用寻找环的入口点ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return NULL; }这个算法背后的数学原理很有趣当快慢指针相遇时让一个指针从头开始与慢指针同速前进再次相遇点就是环入口。3. 链表反转从基础到花式反转反转链表是面试最高频的题目之一我见过至少5种不同的实现方式。最经典的迭代法就像把项链上的珠子一颗颗拆下来重新串ListNode* reverseList(ListNode* head) { ListNode *prev NULL, *cur head; while (cur) { ListNode *next cur-next; cur-next prev; prev cur; cur next; } return prev; }递归解法更体现分治思想ListNode* reverseListRecursive(ListNode* head) { if (!head || !head-next) return head; ListNode *newHead reverseListRecursive(head-next); head-next-next head; head-next NULL; return newHead; }部分反转是进阶版本比如反转第m到第n个节点ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode dummy(0); dummy.next head; ListNode *pre dummy; for (int i 1; i m; i) pre pre-next; ListNode *cur pre-next; for (int i m; i n; i) { ListNode *temp cur-next; cur-next temp-next; temp-next pre-next; pre-next temp; } return dummy.next; }4. 链表排序与合并当链表遇上分治链表排序最经典的是归并排序时间复杂度O(nlogn)。实际写代码时会发现链表版的归并比数组版更简洁因为不需要额外空间。合并两个有序链表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; }链表归并排序的核心是找到中点然后递归ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; // 找中点 ListNode *slow head, *fast head-next; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode *mid slow-next; slow-next NULL; return mergeTwoLists(sortList(head), sortList(mid)); }K个有序链表合并可以用优先队列优化struct Compare { bool operator()(ListNode* a, ListNode* b) { return a-val b-val; } }; ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, Compare pq; for (auto list : lists) if (list) pq.push(list); ListNode dummy(0); ListNode *tail dummy; while (!pq.empty()) { tail-next pq.top(); pq.pop(); tail tail-next; if (tail-next) pq.push(tail-next); } return dummy.next; }5. 特殊链表处理随机指针与深拷贝带随机指针的链表深拷贝是个有趣的挑战。我第一次遇到这个问题时尝试用哈希表存储原节点和拷贝节点的映射关系后来发现更巧妙的节点拆分法。哈希表解法Node* copyRandomList(Node* head) { unordered_mapNode*, Node* map; Node *cur head; while (cur) { map[cur] new Node(cur-val); cur cur-next; } cur head; while (cur) { map[cur]-next map[cur-next]; map[cur]-random map[cur-random]; cur cur-next; } return map[head]; }节点拆分法更省空间Node* copyRandomList(Node* head) { if (!head) return NULL; // 1. 复制节点 Node *cur head; while (cur) { Node *copy new Node(cur-val); copy-next cur-next; cur-next copy; cur copy-next; } // 2. 处理random指针 cur head; while (cur) { if (cur-random) { cur-next-random cur-random-next; } cur cur-next-next; } // 3. 拆分链表 Node *newHead head-next; cur head; while (cur) { Node *temp cur-next; cur-next temp-next; if (temp-next) temp-next temp-next-next; cur cur-next; } return newHead; }6. 链表与其他数据结构的结合链表经常和其他数据结构组合出新的变种比如跳表、块状链表等。在Redis中跳表就是有序集合的底层实现之一。跳表简单实现struct SkipNode { int val; vectorSkipNode* next; SkipNode(int v, int level) : val(v), next(level, nullptr) {} }; class SkipList { int maxLevel; SkipNode *head; public: SkipList() : maxLevel(4) { head new SkipNode(INT_MIN, maxLevel); } int randomLevel() { int level 1; while (rand() % 2 level maxLevel) level; return level; } void insert(int val) { int level randomLevel(); SkipNode *newNode new SkipNode(val, level); SkipNode *cur head; for (int i level-1; i 0; i--) { while (cur-next[i] cur-next[i]-val val) { cur cur-next[i]; } newNode-next[i] cur-next[i]; cur-next[i] newNode; } } };块状链表结合了链表和数组的优点适合文本编辑器等场景struct Block { vectorchar data; Block *next; Block() : next(nullptr) {} }; class BlockList { Block *head; int blockSize; public: BlockList(int size) : blockSize(size), head(new Block()) {} void insert(int pos, char c) { Block *cur head; while (cur pos cur-data.size()) { pos - cur-data.size(); cur cur-next; } if (cur) { cur-data.insert(cur-data.begin() pos, c); if (cur-data.size() blockSize * 2) { splitBlock(cur); } } } void splitBlock(Block *block) { Block *newBlock new Block(); int mid block-data.size() / 2; newBlock-data.assign(block-data.begin() mid, block-data.end()); block-data.erase(block-data.begin() mid, block-data.end()); newBlock-next block-next; block-next newBlock; } };7. 实战案例分析LRU缓存实现LRU缓存淘汰算法是链表应用的经典案例。我曾在项目中用双向链表哈希表实现过比直接使用库提供的LRU性能提升近30%。完整实现struct DLinkedNode { int key, value; DLinkedNode *prev, *next; DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; class LRUCache { unordered_mapint, DLinkedNode* cache; DLinkedNode *head, *tail; int size, capacity; void addToHead(DLinkedNode *node) { node-prev head; node-next head-next; head-next-prev node; head-next node; } void removeNode(DLinkedNode *node) { node-prev-next node-next; node-next-prev node-prev; } void moveToHead(DLinkedNode *node) { removeNode(node); addToHead(node); } DLinkedNode* removeTail() { DLinkedNode *node tail-prev; removeNode(node); return node; } public: LRUCache(int capacity) : capacity(capacity), size(0) { head new DLinkedNode(); tail new DLinkedNode(); head-next tail; tail-prev head; } int get(int key) { if (!cache.count(key)) return -1; DLinkedNode *node cache[key]; moveToHead(node); return node-value; } void put(int key, int value) { if (cache.count(key)) { DLinkedNode *node cache[key]; node-value value; moveToHead(node); } else { DLinkedNode *node new DLinkedNode(key, value); cache[key] node; addToHead(node); size; if (size capacity) { DLinkedNode *removed removeTail(); cache.erase(removed-key); delete removed; size--; } } } };这个实现中双向链表维护访问顺序哈希表提供快速查找所有操作都是O(1)时间复杂度。实际使用时可以根据场景调整容量和淘汰策略。
