[灵感源于算法] 链表类问题技巧总结
[灵感源于算法] 链表类问题技巧总结
@水墨不写bug
文章目录
- 一、链表类题目实用技巧总结
- 1. 动手画图的重要性
- 2. 虚拟头节点技巧
- 3. 多指针辅助技巧
- 4. 快慢双指针技巧
- 二、能力提升题目推荐
- 1、leetcode [2. 两数相加（另一种意义上的大数相加）](https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked)
- 2、leetcode [25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked)
- 3、leetcode [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked)
- 三、总结与建议
一、链表类题目实用技巧总结
1. 动手画图的重要性
- 实用性：链表操作需要精确的指针操作，画图可避免逻辑错误，特别在处理复杂指针重定向时
- 示例：反转链表（可视化指针变化）
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr; // 前驱指针
ListNode *curr = head; // 当前指针
while (curr) {
// 画图示意：A->B->C 变为 A<-B C
ListNode *next = curr->next; // 临时保存下一个节点
curr->next = prev; // 反转指针方向
prev = curr; // 前移prev
curr = next; // 前移curr
}
return prev; // 新链表头
}
图解过程：
初始: 1 → 2 → 3 → ∅
步骤1: ∅ ← 1 2 → 3 → ∅ (prev=1, curr=2)
步骤2: ∅ ← 1 ← 2 3 → ∅ (prev=2, curr=3)
最终: ∅ ← 1 ← 2 ← 3 (prev=3, curr=null)
优势：避免指针丢失错误，清晰展示每一步状态变化
2. 虚拟头节点技巧
- 实用性：消除头节点特殊处理，统一操作逻辑，避免空指针异常
- 示例：删除所有值为
val的节点
ListNode* removeElements(ListNode* head, int val) {
ListNode dummy(0); // 创建虚拟头节点
dummy.next = head;
ListNode* curr = &dummy; // 当前指针指向虚拟头
while (curr->next) {
if (curr->next->val == val) {
ListNode* toDelete = curr->next;
curr->next = curr->next->next; // 跳过待删除节点
delete toDelete; // 释放内存
} else {
curr = curr->next; // 正常后移
}
}
return dummy.next; // 返回真实头节点
}
优势对比：
// 无虚拟头节点的实现（需要额外处理头节点）
ListNode* removeElements(ListNode* head, int val) {
// 特殊处理头节点连续匹配的情况
while (head && head->val == val) {
ListNode* temp = head;
head = head->next;
delete temp;
}
if (!head) return nullptr;
// 处理后续节点
ListNode* curr = head;
while (curr->next) {
if (curr->next->val == val) {
ListNode* temp = curr->next;
curr->next = temp->next;
delete temp;
} else {
curr = curr->next;
}
}
return head;
}
优势：虚拟头节点统一了删除逻辑，代码更简洁，避免重复处理头节点
3. 多指针辅助技巧
- 实用性：使用额外指针简化复杂操作，避免指针操作顺序错误
- 示例：在排序链表中插入节点
ListNode* insertNode(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
// 情况1：插入到头节点前面
if (!head || val < head->val) {
newNode->next = head;
return newNode;
}
// 使用双指针：prev跟踪前驱，curr遍历
ListNode *prev = head;
ListNode *curr = head->next;
while (curr && curr->val < val) {
prev = curr;
curr = curr->next;
}
// 插入到prev和curr之间
prev->next = newNode;
newNode->next = curr;
return head;
}
优势：使用prev和curr两个指针，避免在单指针方案中需要记住前驱节点的麻烦
4. 快慢双指针技巧
- 实用性：解决链表中的位置关系问题，时间复杂度O(N)，空间复杂度O(1)
- 应用1：检测环形链表及环入口
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
// 第一阶段：检测环是否存在
while (fast && fast->next) {
slow = slow->next; // 慢指针走1步
fast = fast->next->next; // 快指针走2步
if (slow == fast) break; // 相遇说明有环
}
// 无环情况
if (!fast || !fast->next) return nullptr;
// 第二阶段：查找环入口
slow = head; // 慢指针重置到头
while (slow != fast) {
slow = slow->next; // 两者同步前进
fast = fast->next;
}
return slow; // 相遇点即为环入口
}
- 应用2：查找倒数第K个节点
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *fast = head, *slow = head;
// fast先走k步
for (int i = 0; i < k; ++i) {
if (!fast) return nullptr; // 链表长度不足k
fast = fast->next;
}
// 同步移动直到fast到达末尾
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // slow指向倒数第k个节点
}
- 应用3：找到链表中点（奇数为中点，偶数为上中点）
ListNode* findMiddle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next && fast->next->next) {
slow = slow->next; // 慢指针走1步
fast = fast->next->next; // 快指针走2步
}
return slow;
}
二、能力提升题目推荐
1、leetcode 2. 两数相加（另一种意义上的大数相加）
逆序链表数字相加，其实逆序更加好做。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1,*cur2 = l2,*phead = new ListNode(0),*prev = phead;
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);
t /= 10;
prev = prev->next;
}
ListNode* ret = phead->next;
delete phead;
return ret;
}
};
2、leetcode 25. K 个一组翻转链表
有难度的一道题目，主要思想是：
先统计需要反转多少次，接下来进行
1、同时维护两个链表；
2、头插pcur，pcur再移动到尾部，重复循环头插
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
/*整体思路：K个一组进行头插，k个插完之后，pcur移动到末尾，再次循环进行k个一组进行头插
最后不满k个一组的，不用改变链表的结构，放在后面直接链入最终结果链表*/
ListNode* phead = new ListNode(-1),*cur = head,*pcur = phead;//pcur自己维护一个链表
int count = 0;
while(cur)//统计整体节点个数
{
++count;
cur = cur->next;
}
int sp = count / k;//一共需要反转的轮数
cur = head;//重置cur到head节点
while(sp--)
{
for(int i = 0;i < k;++i)
{
ListNode* next = cur->next,*pnext = pcur->next;//p：表示pcur维护的答案链表
pcur->next = cur;
cur->next = pnext;
cur = next;
}
while(pcur->next)
pcur = pcur->next;
}
pcur->next = cur;//把剩余的部分接入答案链表中
ListNode* ret = phead->next;
delete phead;
return ret;
}
};
3、leetcode 24. 两两交换链表中的节点
其实就是上一题的k==2的特殊情况，但是针对这一题实现的逻辑会更加简单
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* phead = new ListNode(0);//头节点，简化逻辑
phead->next = head;
ListNode* cur = head,*next = head->next,*prev = phead;
while(cur && cur->next)
{
cur->next = next->next;
next->next = cur;
prev->next = next;
prev = cur;
cur = cur->next;
if(cur)
next = cur->next;
}
cur = phead->next;
delete phead;
return cur;
}
};
三、总结与建议
- 画图先行：在纸上画出初始状态、目标状态和中间步骤，特别是涉及多个指针的操作
- 虚拟头节点：当操作可能改变头节点时，优先考虑使用
dummy node - 多指针策略：
- 使用
prev/curr处理插入/删除 - 使用
curr/next避免指针丢失 - 复杂操作时创建临时指针保存关键节点
- 使用
- 快慢指针应用场景：
- 环检测：快慢指针是否相遇
- 环入口：相遇后重置慢指针
- 中点查找：快指针到末尾时慢指针位置
- 倒数第K个：快指针先走K步
- 链表相交：双指针走不同路径
完~
未经作者同意禁止转载
本文地址：https://www.vps345.com/14506.html
上一篇：重构前端代码，定义开发规划
