C++算法学习——链表
·
本篇我们来学习C++算法思想中一个很重要的专题：链表。链表不仅仅是算法竞赛中常见的算法，而且在企业笔试面试中也是不可或缺的一环。
相关题解代码已经上传至作者的个人gitee中：楼田莉子/C++算法学习，喜欢请支持一下谢谢
目录
前言
链表的基本概念
链表是一种线性数据结构，与数组不同，它通过指针将一组零散的内存块串联起来使用。每个内存块称为一个"节点"(Node)，每个节点包含两部分：
- 数据域：存储实际的数据
- 指针域：存储指向下一个节点的地址
链表的典型应用
- 操作系统：文件系统的目录结构、内存管理
- 数据库系统：实现索引结构
- 浏览器：网页的前进后退功能
- 游戏开发：场景中的对象管理
- 编译器设计：符号表的管理
企业面试中的常见链表问题
根据面试经验，高频链表问题包括但不限于：
- 链表反转(单链表、部分反转)
- 链表环检测及环入口查找
- 合并两个有序链表
- 删除倒数第N个节点
- 链表排序(要求O(nlogn)时间复杂度)
- 复杂链表的复制(带随机指针的链表)
- 链表相交问题
链表常用的操作和技巧总结
常用技巧
1、画图（重点！！！）
2、引入虚拟头节点
3、大胆去定义变量
4、快慢双指针
常见操作
1、创建新节点
2、尾插
3、头插
1、两数相加
算法原理：模拟两数相加的过程
/**
* 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;
}
};2、两两交换链表中的节点
算法原理：
算法一：递归回溯算法
这里简单介绍一下
-
步骤：
-
递归终止条件：如果链表为空或只有一个节点，无法交换，直接返回。
-
递归调用：处理当前两个节点后的剩余链表（即从第三个节点开始递归）。
-
回溯交换：在回溯过程中，交换前两个节点，并将交换后的节点与递归处理的结果连接。
-
/**
* 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* rest = swapPairs(head->next->next);
// 回溯交换：交换前两个节点
ListNode* second = head->next; // 记录第二个节点
second->next = head; // 第二个节点指向第一个节点
head->next = rest; // 第一个节点指向递归处理后的链表
// 返回新的头节点（原第二个节点）
return second;
}
};算法二：循环迭代（模拟）
/**
* 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;
next->next=cur;
cur->next=nnext;
//修改指针
prev=cur;
cur=nnext;
if(cur) next=cur->next;
if(next) nnext=next->next;
}
cur=newhead->next;
delete newhead;
return cur;
}
};3、重排链表
算法思想：
1、找到链表中间节点（快慢双指针·）
2、后半部分逆序（三指针或者头插）
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:
void reorderList(ListNode* head)
{
if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return ;
//找到链表中间节点（一定要画图考虑slow的落点）
ListNode*fast=head,*slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
//slow后面部分逆序——头插法
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;
}
};4、合并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 {
public:
//算法一（推荐）
struct cmp
{
bool operator()(const ListNode*list1,const ListNode*list2)
{
return list1->val > list2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists)
{
//创建小根堆
priority_queue<ListNode*,vector<ListNode*>,cmp>heap;
//所有结点进入小根堆
for(auto& x:lists)
if(x) heap.push(x);
//合并k个有序链表
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;
}
};算法二：分治——递归
/**
* 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* merge(vector<ListNode*>&lists,int left,int right)
{
if(left>right) return nullptr;
if(left==right) return lists[left];
//平分数组
int mid=left+(right-left)/2;
//[left,mid][mid+1,right]
//递归处理做有区间
ListNode* l1= merge(lists,left,mid);
ListNode* l2= merge(lists,mid+1,right);
//合并两个有序链表
return mergeTwolist(l1,l2);
}
ListNode* mergeTwolist(ListNode*l1,ListNode*l2)
{
if(l1==nullptr) return l2;
if(l2==nullptr) return l1;
//合并两个链表
ListNode head;
ListNode*cur1=l1,*cur2=l2,*prev=&head;
head.next=nullptr;
while(cur1&&cur2)
{
if(cur1->val<=cur2->val)
{
prev=prev->next=cur1;
cur1=cur1->next;
}
else
{
prev=prev->next=cur2;
cur2=cur2->next;
}
}
if(cur1) prev->next=cur1;
if(cur2) prev->next=cur2;
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
return merge(lists,0,lists.size()-1);
}
};
5、k个一组翻转链表
算法思想：模拟
1、先求出逆序多少组
2、重复n次长度为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 {
public:
ListNode* reverseKGroup(ListNode* head, int k)
{
//先求逆序次数
int n=0;
ListNode*cur=head;
while(cur)
{
cur=cur->next;
n++;
}
n/=k;
//重复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;
}
};本期内容就到这里结束了，喜欢请点个赞谢谢。
更多推荐
33
0- 0
已为社区贡献17条内容
所有评论(0)