链表算法专题：常用技巧与经典题目解析

1、链表类算法题常用技巧

【技巧】

1. 画图：直观 + 形象 + 便于理解。
2. 引入虚拟头节点：链表类型算法题通常是不带头节点的单向链表，从第一个位置开始存储有效数据。引入不存储数据的哨兵节点，便于处理边界情况，方便操作。
3. 大胆定义变量：直接定义指针保存节点，避免担心语句执行顺序导致丢失。
4. 快慢双指针：适用于判断链表是否有环、找环入口、找倒数第 n 个节点。

【链表中的常用操作】

1. 创建一个新节点 new。
2. 尾插：先定义变量指向尾节点，tail->next = 新节点，tail 指向新节点（初始化时尾指针指向最后一个节点）。
3. 头插：使用虚拟头节点，让新节点的 next 指向虚拟头节点的 next，然后让虚拟头节点的 next 指向新节点。头插法可直接用于逆序链表。

*只需定义一个 cur，再完成头插即可实现逆序链表。

【注意】链表题一定要特别注意空节点！*

2、2.两数相加

题目解析：

输入为逆序存储的链表数字，例如 342+465=807，返回 708。逆序存储方便从最低位开始相加，对应链表的低位节点。

思路：

先创建虚拟头节点 newhead，初始化 t 用来存储两数加的结果。将 cur1 和 cur2 的值累加到 t 中，求出 t 的个位，创建新节点放入结果链表尾部。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1 = l1, *cur2 = l2; ListNode* newhead = new ListNode(0); // 创建虚拟头节点 ListNode* prev = newhead; // 尾指针 int t = 0; // 记录进位 while(cur1 || cur2 || t) { if(cur1) { t += cur1->val; cur1 = cur1->next; } if(cur2) { t += cur2->val; cur2 = cur2 -> next; } prev->next = new ListNode(t % 10); prev = prev->next; t /= 10; } prev = newhead->next; delete newhead; return prev; } };

3、24.两两交换链表中的节点

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* newhead = new ListNode(0); newhead->next = head; ListNode* prev = newhead, *cur = prev->next, *next = cur->next, *nnext = next->next; while(cur && next) { prev->next = next; cur->next = nnext; next->next = cur; prev = cur; cur = nnext; if(cur) next = cur->next; if(next) nnext = next->next; } cur = newhead->next; delete newhead; return cur; } };

4、143.重排链表

题意： 输出第一个，倒数第一个，第二个，倒数第二个这样输出。

算法思想： 模拟。

1. 找到链表的中间节点（使用快慢指针）。
2. 把后面的部分逆序（头插法）。
3. 合并两个链表（使用双指针）。

分类讨论： 当链表元素有奇数个时，slow 指针刚好指向中间；偶数个时，slow 指向中间偏右。对后半部分链表进行反转操作，包含 slow 所指向的节点一起反转均适用。若拆分链表需注意断开连接，建议加虚拟头节点。

步骤：

• 第二步：反转（头插 + 虚拟头节点）。
• 第三步：合并（尾插 + 虚拟头节点 + 尾指针）。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return; ListNode* slow = head, *fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* head2 = new ListNode(0); ListNode* cur = slow->next; slow->next = nullptr; while(cur) { ListNode* next = cur->next; cur->next = head2->next; head2->next = cur; cur = next; } ListNode* ret = new ListNode(0); ListNode* prev = ret; ListNode* cur1 = head, *cur2 = head2->next; while(cur1) { prev->next = cur1; cur1 = cur1->next; prev = prev->next; if(cur2) { prev->next = cur2; cur2 = cur2->next; prev = prev->next; } } delete head2; delete ret; } };

5、23.合并 K 个升序链表

利用优先级队列： 创建一个小根堆，使用 k 个指针，先指向第一个节点，把这些元素全放进小根堆当中。拿出堆顶的元素，如果这个节点的后面还有节点就放到堆里。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { return l1->val > l2->val; } }; public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*,vector<ListNode*>, cmp> heap; for(auto l : lists) if(l) heap.push(l); ListNode* ret = new ListNode(0); ListNode* prev = ret; while(!heap.empty()) { ListNode* t = heap.top(); heap.pop(); prev->next = t; prev = t; if(t->next) heap.push(t->next); } prev = ret->next; delete ret; return prev; } };

6、25.K 个一组翻转链表

思路：

1. 先求出需要逆序多少组：n = 长度/k。
2. 重复 n 次，长度为 k 的链表的逆序（链表逆序用头插法）。
3. 注意：当反转完一组之后，进入下一组的时候，不能把下一组的元素放到上一组的前面。进入每组的反转循环时，先记录一下第一个节点，当这组反转完之后，把下组放在这个节点的后面开始头插。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { int n = 0; ListNode* cur = head; while(cur) { cur = cur->next; n++; } n /= k; ListNode* newhead = new ListNode(0); ListNode* prev = newhead; cur = head; for(int i = 0; i < n; i++) { ListNode* tmp = cur; for(int j = 0; j < k; j++) { ListNode* next = cur->next; cur->next = prev->next; prev->next = cur; cur = next; } prev = tmp; } prev->next = cur; cur = newhead->next; delete newhead; return cur; } };