跳到主要内容剑指 Offer 第 2 版:链表核心算法实战解析 | 极客日志C++算法
剑指 Offer 第 2 版:链表核心算法实战解析
链表系列是面试高频考点,本文涵盖剑指 Offer 中的经典题目,包括反转打印、节点删除、去重、倒数第 K 个节点、链表反转、合并排序链表、公共节点查找、复杂链表复制以及环的检测与入口。通过递归、栈、双指针、哈希表等多种技巧,深入解析不同场景下的最优解法及边界条件处理,适合准备面试的开发者系统复习。
从尾到头打印链表
这道题考察的是对链表遍历顺序的灵活处理。常见的思路有三种。
递归法
利用递归的特性,先访问后续节点,回溯时再记录当前值。这种方式代码简洁,但要注意如果链表过长,递归深度过深可能导致栈溢出。
class Solution {
public:
void print(vector<int>&ret, ListNode* head){
if(head==nullptr) return;
print(ret,head->next);
ret.emplace_back(head->val);
}
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ret;
print(ret,head);
return ret;
}
};
栈法
利用栈后进先出的特性,先将所有节点入栈,再依次出栈存入数组。这样可以避免递归带来的栈溢出风险,但会消耗额外的内存空间。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(!head) return {};
stack<int> st;
vector<int> ret;
while(head){
st.push(head->val);
head=head->next;
}
while(!st.empty()){
ret.emplace_back(st.top());
st.pop();
}
return ret;
}
};
逆序法
既然最终需要返回数组,可以直接遍历链表存入数组,最后调用标准库的 reverse 函数进行逆序。这是最直观且效率较高的方法。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(!head) return {};
vector<int> ret;
while(head) {
ret.emplace_back(head->val);
head=head->next;
}
reverse(ret.begin(),ret.end());
return ret;
}
};
删除链表的节点
删除指定值的节点时,关键在于找到待删除节点的前驱节点。如果是头节点被删除,直接返回 head->next 即可;否则需要遍历找到前驱并修改指针。
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return nullptr;
if(head->val==val) return head->next;
ListNode* cur=head;
while(cur->next&&cur->next->val!=val)
cur=cur->next;
cur->next=cur->next->next;
return head;
}
};
删除排序链表中的重复节点
对于有序链表去重,使用哨兵节点(虚拟头结点)可以简化边界条件的处理,特别是当整个链表都是重复节点的情况。采用前后指针配合,判断连续重复区间,跳过这些区间即可。
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead==nullptr) return nullptr;
ListNode*newhead=new ListNode(0);
newhead->next=pHead;
ListNode* prev=newhead;
ListNode* rear=pHead;
while(rear!=nullptr){
while(rear->next&&rear->val!=rear->next->val){
prev=prev->next;
rear=rear->next;
}
while(rear->next&&rear->val==rear->next->val)
rear=rear->next;
if(prev->next!=rear)
prev->next=rear->next;
rear=rear->next;
}
return newhead->next;
}
};
链表中倒数第 k 个结点
双指针是解决此类问题的利器。让快指针先走 k 步,然后快慢指针同时移动,当快指针到达末尾时,慢指针正好指向倒数第 k 个节点。注意处理 k 大于链表长度或 k 为 0 的边界情况。
class Solution {
public:
ListNode* FindKthToTail(ListNode* head, int k) {
if(!head||k==0) return nullptr;
ListNode*fast,*slow;
fast=slow=head;
while(k>0&&fast){
fast=fast->next;
--k;
}
while(fast){
fast=fast->next;
slow=slow->next;
}
return k>0?nullptr:slow;
}
};
反转链表
反转链表主要有两种经典写法:三指针迭代法和头插法。
三指针法
定义三个指针分别指向当前节点、前一个节点和后一个节点,在遍历过程中逐个翻转指针方向。这种方法逻辑清晰,不易断链。
class Solution {
public:
ListNode* ReverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode*p1=head;
ListNode*p2=head->next;
ListNode*p3=head->next->next;
while(p3){
p2->next=p1;
p1=p2;
p2=p3;
p3=p3->next;
}
p2->next=p1;
head->next=nullptr;
return p2;
}
};
头插法
维护一个新链表的头节点,将原链表节点依次摘下来插入到新链表头部。实现起来非常简洁。
class Solution {
public:
ListNode* ReverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode*newhead=nullptr;
while(head){
ListNode* t=head;
head=head->next;
t->next=newhead;
newhead=t;
}
return newhead;
}
};
合并两个排序的链表
归并两个有序链表,可以使用哨兵节点辅助构建新链表,或者直接使用递归。
迭代法
设置一个哨兵节点作为新链表的起点,比较两个链表当前节点的值,将较小的节点链接到结果链表尾部,直到其中一个链表为空。
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(!pHead1) return pHead2;
if(!pHead2) return pHead1;
ListNode*newhead=new ListNode(-1);
ListNode*rear=newhead;
while(pHead1&&pHead2){
if(pHead1->val<pHead2->val){
rear->next=pHead1;
pHead1=pHead1->next;
} else{
rear->next=pHead2;
pHead2=pHead2->next;
}
rear=rear->next;
}
if(!pHead1) rear->next=pHead2;
if(!pHead2) rear->next=pHead1;
return newhead->next;
}
};
递归法
递归逻辑更直观:比较头节点,较小的那个节点的 next 指向剩余部分的合并结果。
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if (!pHead1) return pHead2;
if (!pHead2) return pHead1;
if (pHead1->val < pHead2->val) {
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
} else {
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
两个链表的第一个公共节点
单链表若有公共节点,则从该节点开始后续路径完全重合。因此可以从尾部往前找,或者通过计算长度差对齐后同步查找。
哈希表法
将第一个链表的所有节点地址存入集合,遍历第二个链表时检查是否存在于集合中。空间复杂度较高,但逻辑简单。
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
if (!pHead1 || !pHead2) return nullptr;
if(pHead1==pHead2) return pHead1;
unordered_set<ListNode*> s;
while(pHead1){
s.insert(pHead1);
pHead1=pHead1->next;
}
while(pHead2){
if(s.count(pHead2)) return pHead2;
pHead2=pHead2->next;
}
return nullptr;
}
};
长度差法
先计算两个链表的长度和尾部节点是否相同。若尾部不同则无交点;若尾部相同,则让长链表先走差值步,再同步前进,相遇点即为交点。
class Solution {
public:
ListNode* getlenth(ListNode* cur, int& count) {
while (cur->next) { ++count; cur = cur->next; }
return cur;
}
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
if (!pHead1 || !pHead2) return nullptr;
int count1 = 0, count2 = 0;
ListNode* end1 = getlenth(pHead1, count1);
ListNode* end2 = getlenth(pHead2, count2);
if (end1 != end2) return nullptr;
if (count1 > count2)
while (count1 - count2) { --count1; pHead1 = pHead1->next; }
else
while (count2 - count1) { --count2; pHead2 = pHead2->next; }
while (pHead1 != pHead2) {
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return pHead1;
}
};
复杂链表的复制
复杂链表包含随机指针 random。难点在于如何高效地建立 random 指针的映射关系。
拼接法
将新节点插入到原节点之后,形成 A->A'->B->B' 的结构。这样可以通过原节点的 random 快速定位新节点的 random(即 random->next),最后再将链表拆分为两条。
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if(!pHead) return nullptr;
RandomListNode* cur=pHead;
while(cur){
RandomListNode*newnode =new RandomListNode(cur->label);
newnode->next=cur->next;
cur->next=newnode;
cur=cur->next->next;
}
cur=pHead;
while(cur){
if(cur->random) cur->next->random=cur->random->next;
cur=cur->next->next;
}
RandomListNode*newhead=new RandomListNode(-1);
RandomListNode*newtail=newhead;
cur=pHead;
while(cur){
RandomListNode*temp=cur->next;
cur->next=cur->next->next;
newtail->next=temp;
newtail=newtail->next;
cur=cur->next;
}
return newhead->next;
}
};
哈希表法
第一次遍历创建新节点并建立原节点到新节点的映射表,第二次遍历根据映射表设置 random 指针。空间换时间,逻辑更解耦。
#include <unordered_map>
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if(!pHead) return nullptr;
unordered_map<RandomListNode*,RandomListNode*> hash;
RandomListNode*newhead,*newtail;
newtail=newhead=nullptr;
RandomListNode* cur=pHead;
while(cur){
RandomListNode*newnode =new RandomListNode(cur->label);
hash[cur]=newnode;
if(!newtail) newtail=newhead=newnode;
else{
newtail->next=newnode;
newtail=newtail->next;
}
cur=cur->next;
}
cur=pHead;
RandomListNode* copy=newhead;
while(cur){
if(cur->random) copy->random=hash[cur->random];
cur=cur->next;
copy=copy->next;
}
return newhead;
}
};
链表中环的检测与入口
检测环
使用快慢指针,快指针每次走两步,慢指针每次走一步。如果有环,两者必会在环内相遇;若无环,快指针会先到达空节点。
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head||!head->next) return false;
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow) return true;
}
return false;
}
};
环的入口
基于数学推导,从链表头到入口的距离等于从相遇点到入口的距离。找到相遇点后,让一个指针从头开始,另一个从相遇点开始,同速前进,再次相遇点即为入口。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(!pHead||!pHead->next) return nullptr;
ListNode*fast =pHead;
ListNode*slow =pHead;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow) break;
}
if(fast!=slow) return nullptr;
while(pHead!=fast){
pHead=pHead->next;
fast=fast->next;
}
return pHead;
}
};
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online