跳到主要内容剑指 Offer 第 2 版：链表算法详解 | 极客日志C++算法
剑指 Offer 第 2 版：链表算法详解
整理自剑指 Offer 第 2 版链表专题，包含从尾到头打印、删除节点、去重、倒数第 K 个节点、反转、合并、公共节点、复杂链表复制、环检测及入口节点查找等十道经典算法题。通过递归、栈、双指针、哈希表等多种方法提供 C++ 代码实现，解析了哨兵节点、快慢指针等核心解题技巧与边界条件处理。
极客零度0 浏览 
一、JZ6 从尾到头打印链表（递归/栈）
解法 1：递归，每访问一个节点时，先递归输出它后面的节点，再输出该节点自身。但可能导致函数调用层级很深，从而导致栈溢出。
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;
}
};
解法 2：利用栈后进先出的特性，可以避免栈溢出的情况，但是会消耗一部分内存。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(!head) return {};
stack<> st;
vector<> ret;
(head){
st.(head->val);
head=head->next;
}
(!st.()){
ret.(st.());
st.();
}
ret;
}
};
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如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
int
int
while
push
while
empty
emplace_back
top
pop
return
解法 3：因为该题返回数组，所以直接保存在数组里然后直接逆序即可！
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;
}
};
二、JZ18 删除链表的节点
因为我们需要找到前面的节点链接后面的节点，所以我们必须停留在该节点的前一个节点。
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;
}
};
三、扩展 JZ18 删除排序链表的重复节点（前后指针）
我们要用两个指针，左开右闭。这里要考虑特别多的特殊情况，如：全部相同，全部不相同，部分相同等。为了方便解题我们定义哨兵头结点，主要是应对全部相同的情况。
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;
}
};
四、JZ22 链表中倒数第 k 个结点（前后指针）
可以遍历两次链表，第一次链表算长度，然后根据长度算出倒数第 k 个是第几个，然后第二次再去找，但是还有更好的方法只需要遍历一次链表即可。
可以定义两个指针，一个指针先走 k 步，再让另一个指针跟在后面，使用'前后指针'的方式，当前面的指针到达结尾，后面的指针，也就是倒数第 k 个节点（但是要注意 k 超过节点数的情况）。
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;
}
};
注意 k 是无符号整数，如果是 0 的话，一定不能让他 -1。
五、JZ24 反转链表（三指针/头插）
1、定义三个指针，整体右移，边移动，边翻转，保证不会断链。
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;
}
};
六、JZ25 合并两个排序的链表（双指针/递归）
思路 1：可以一个一个节点的归并，可以搞一个哨兵节点。
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;
}
};
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;
}
}
};
七、JZ52 两个链表的第一个公共节点 (双指针/栈/set)
题目要求是单链表，每个节点只有一个 next 指针，因此从第一个公共节点开始，之后他们所有的节点都是重合的，不可能再出现分叉！
我们会发现如果两个链表有公共节点，那么至少链表的尾部一定是公共节点，那么如果能够从尾部开始走那么最后一个相同的节点就是第一个公共节点，但是因为单链表不可能从尾部开始走，所以这里我们就必须借助栈结构'后进先出'的特性！！
方法 1：借助两个辅助栈，然后将节点全部丢到栈里面，然后从栈顶开始遍历直到找到最后一个相同的节点。
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
if (!pHead1 || !pHead2) return nullptr;
if(pHead1==pHead2) return pHead1;
stack<ListNode*> st1;
stack<ListNode*> st2;
while(pHead1){
st1.push(pHead1);
pHead1=pHead1->next;
}
while (pHead2) {
st2.push(pHead2);
pHead2=pHead2->next;
}
if(st1.top()!=st2.top()) return nullptr;
while(!st1.empty()&&!st2.empty()){
ListNode* t1=st1.top(),*t2=st2.top();
st1.pop();
st2.pop();
if(st1.empty()||st2.empty()||st1.top()!=st2.top()) return t1;
}
return nullptr;
}
};
方法 2：本质是让长的链表先走 abs（length1-length2）步，后面大家的步调一致，往后找第一个地址相同的节点，就是题目要求的节点，所以需要各自遍历两次链表。
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;
}
};
方法 3：直接把其中一个链表节点都保存到 set 里面，然后遍历另一个链表，只要出现了就返回
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;
}
};
八、JZ35 复杂链表的复制 (模拟/哈希)
该题的难点就在于如果直接拷贝，那么 random 指针要拷贝的话还需要去原链表里面一次次遍历长度才可以，此时的时间复杂度是 n^2。因此我们在创建节点的时候，将新的节点连接在原链表后面，然后修改 random 指针之后，再把链表拆开！！
方法 1：模拟，让新表接在原表的后面，然后修改 random 指针之后，再把表拆下来返回
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 指针指向节点而产生的效率问题，所以我们把他接在原链表的节点后面是为了方便通过原链表快速修改 random 指针，那么如果我们可以直接让新节点和原节点建立联系呢？？比如说通过哈希表建立映射关系！！
方法 2：哈希，第一次遍历创建新链表和原链表每个节点的映射关系，第二遍去改 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;
}
};
九、扩展 JZ23 链表判环（快慢指针）
如果链表有环的话，那么用快慢指针，fast 会逐步接近追上 slow，如果无环那么 fast 最后会走向空
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;
}
};
十、JZ23 链表中环的入口节点（快慢指针 + 环性质）
解法 1：利用相遇点到入口点的距离=链表头到入口点的距离 这个性质
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;
}
};
解法 2：在相遇点将链表拆开，转化成两个链表的找第一个相交节点的问题
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;
}
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;
fast=fast->next;
slow->next=nullptr;
return FindFirstCommonNode(pHead,fast);
}
};
