深度解析算法之链表
52.两数相加
题目链接 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入： l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释： 342 + 465 = 807.
示例 2：
输入： l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
这个代码是我们之前做的，使用的是c语言进行解决的
/**
* 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:
//思路：我们对两个链表同时进行对应节点相加的操作
//如果相加的时候我们的两个数相加的大小大于10的话，那么我们就进行进位的操作，
//使用/获取进位的数
//然后在下一次循环的时候那么这个进位的数就会被加进去了
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
//先创建一个哨兵位
ListNode *newhead=new ListNode();
ListNode *cur1=l1,*cur2=l2,*tail=newhead;
//我们这里在循环遍历两个链表的同时，将对应节点的数字进行相加的操作，然后进行新的链表的创建操作
int t=0;//t是用来保存两个链表中对应节点相加的值
while(cur1||cur2)//只要有一个链表不为空我们就进行这个循环操作
{
if(cur1)//如果cur1不是空的话
{
t+=cur1->val;
cur1=cur1->next;
}
if(cur2)//如果cur2不是空的话
{
t+=cur2->val;
cur2=cur2->next;
}
//我们进行新的链表的创建操作，里面的值使用我们相加的值
tail->next=new ListNode(t%10);//使用%保存个位上的数
t/=10;//处理进位的操作,存在下次循环的t中了
tail=tail->next;
}
//循环结束的话，如果t里面还有进位的数字的话，那么我们就再申请一个节点就行了
if(t)//如果t需要进位的话，我们创建下一个节点，将当前进位的数字存在下个节点中，然后从下个节点开始进行操作
{
tail->next=new ListNode(t);
}
return newhead->next;//将头结点返回就行了
//这个newhead是一个哨兵位
}
};
/*
假如说当前的节点相加的是6和7的话
那么我们就会申请一个3的节点，然后t就变成了1
向前进位了
下次操作的时候我们的t就是这个1了，我们从1开始操作的
*/那么我们思路就是定义一个cur1和cur2指向两个链表的头结点 定义一个变量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)//循环的条件就是我们的cur1和cur2不能都为空，只要一个链表存在数据的话，那么我们的循环就继续操作，并且我们的t也不能为0，只要有数据的话，我们都得继续循环
{
//先加上第一个链表
if(cur1)//我们的cur1这个链表不为空的话，我们就加上
{
t+=cur1->val;//将当前cur1中的数据加到t中
cur1=cur1->next;//cur1往后面进行移动
}
//加上第二个链表
if(cur2)//我们的cur2这个链表不为空的话，我们就加上
{
t+=cur2->val;//将当前cur2中的数据加到t中
cur2=cur2->next;//cur2往后面进行移动
}
prev->next=new ListNode(t%10);//将t的个位保存在我们的节点中
prev=prev->next;//进行节点的更新操作
t/=10;
}
prev=newhead->next;//存一下我们的真实的返回结果
delete newhead;//释放我们的虚拟节点
return prev;//我们最终返回的链表就是这个虚拟节点的后一个节点带头的
}
};遍历两个链表，分别进行遍历操作，在每次遍历的时候我们将节点中的值加上，并且进行进位的操作
53.两两交换链表中的节点
题目链接 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入： head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入： head = [] 输出：[]
示例 3：
输入： head = [1] 输出：[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* 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;//这里的话前提是我们的cur不为空的情况
if(next)nnext=next->next;//next不为空的话，那么我们就修改指针
}
cur=newHead->next;
delete newHead;
return cur;
}
};我们按照上面的图的流程来就行了
54.重排链表
题目链接
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1：
输入： head = [1,2,3,4] 输出：[1,4,2,3]
示例 2：
输入： head = [1,2,3,4,5] 输出：[1,5,2,4,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 ;
//1.找到链表的中间节点---快慢双指针（一定要考虑slow的落点在哪里）
ListNode*slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
//当循环结束之后，我们的slow就落在了中间节点了
//如果我们的节点的个数是偶数的话，那么slow最后的落点就是中间位置靠右的那个节点
//如果我们的节点个数是奇数的话，那么slow最后的落点是中间节点
//我们尽量对奇数和偶数的处理方式保持一样
//我们可以将slow后面的进行逆序，我们也可以从slow的位置逆序，都是可行的，但是推荐使用slow->next开始进行逆序
//2.将slow后面的部分进行逆序操作---头插法
ListNode*head2=new ListNode(0);//创建一个哨兵位
ListNode*cur=slow->next;//从slow->next开始进行逆置操作
slow->next=nullptr;//注意将两个链表给断开
//头插操作
while(cur)//cur不为空的话，那么我们就进行
{
ListNode*next=cur->next;//标记一下
cur->next=head2->next;//cur的next指向我们的哨兵位的下个节点
head2->next=cur;//哨兵位的下个节点指向cur
cur=next;//cur更新为next继续进行while循环
}
//到这里剩下的那部分就已经逆序完毕了
//3.合并两个链表---双指针
ListNode*ret=new ListNode(0);//创建一个哨兵位
ListNode*prev=ret;
ListNode*cur1=head;
ListNode*cur2=head2->next;
while(cur1)//当我们的cur1不为空的话就一直进行合并的操作，因为我们cur1这部分是比较长的，因为我们在从中点开始断开的时候选择的是slow后面的节点开始断开的
{
//先放第一个链表
prev->next=cur1;
cur1=cur1->next;
prev=prev->next;
//再放第二个链表
if(cur2)//有可能我们的cur2为空了，那么我们就不放了
{
prev->next=cur2;
cur2=cur2->next;
prev=prev->next;
}
}
delete head2;
delete ret;
}
};找到链表的中间节点—快慢双指针，落点的话我们考虑slow后面的那个节点开始，从那个节点开始进行逆置操作
将slow后面的部分进行逆序操作—头插法
合并两个链表—双指针
下面的代码很有说法
55.合并 K 个升序链表
题目链接 给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1：
输入： lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释： 链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入： lists = [] 输出：[]
示例 3：
输入： lists = [[]] 输出：[]
解法一：暴力解法，时间复杂度超时
解法二：利用优先级队列做优化
/**
* 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,ListNode*l2)
{
return l1->val>l2->val;//当l1的值大于l2的值我们就进行向下调整的操作
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
//创建一个小根堆
priority_queue<ListNode*,vector<ListNode*>,cmp>heap;
//让所有的头节点进入小根堆
for(auto l:lists)
if(l)heap.push(l);//如果头结点不为空的话，那么我们就进入到小根堆
//合并k个有序列表
ListNode*ret=new ListNode(0);//先创建一个虚拟的头结点
ListNode*prev=ret;
while(!heap.empty())//当堆不为空的话，我们一直拿出堆顶的元素
{
auto t=heap.top();//获取堆顶元素
heap.pop();//删除堆顶元素
prev->next=t;
prev=t;//prev移动到t的位置
if(t->next) heap.push(t->next);//如果t后面的节点不为空的话，我们将后面的节点加入到堆中,如果 `t` 有下一个节点，我们就把 `t->next` 加入到优先队列（堆）中，确保堆中永远有下一个最小的节点参与到合并过程中。
}
prev=ret->next;
delete ret;
return prev;
}
};这个 cmp 结构体是用来定义优先队列中的排序规则的。它告诉优先队列如何比较两个链表节点的值。这里的排序规则是升序排列，即当 l1 的值大于 l2 的值时，l1 会排在后面。
struct cmp {
bool operator()(const ListNode* l1, ListNode* l2) {
return l1->val > l2->val; // 当 l1 的值大于 l2 的值时返回 true
}
};使用一个 priority_queue（优先队列）来保存链表节点。这里使用了自定义的比较器 cmp，所以这个优先队列会按照节点的值进行升序排序。
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;if(t->next) heap.push(t->next);如果 t 有下一个节点，我们就把 t->next 加入到优先队列（堆）中，确保堆中永远有下一个最小的节点参与到合并过程中。
解法三：分治—递归
递归一直向下进行延伸，当我们不能继续向下延伸之后了，我们就开始向上合并了
每一层的链表会执行logk次合并，其中每个合并都是合并k个链表，每一个链表都有n个节点
/**
* 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* mergeKLists(vector<ListNode*>& lists)
{
return merge(lists,0,lists.size()-1);//从n~n-1个链表开始进行合并操作
}
ListNode*merge(vector<ListNode*>&lists,int left,int right)
{
if(left>right)return nullptr;//说明这个区间不存在
if(left==right) return lists[left];//说明只存在一个链表
//1.平分数组
int mid=(left+right)>>1;
//[left,mid][mid+1,right]
//2.递归处理左右区间
ListNode* l1=merge(lists,left,mid);//合并之后将返回的结果存在l1中
ListNode* l2=merge(lists,mid+1,right);//合并之后将返回的结果存在l2中
//3.合并两个有序链表
return mregeTowList(l1,l2);
}
ListNode*mregeTowList(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->next=cur1;
prev=cur1;//进行prev的更新操作
cur1=cur1->next;
}
else
{
prev->next=cur2;
prev=cur2;//进行prev的更新操作
cur2=cur2->next;
}
}
//当循环结束之后，肯定有一个链表合并完成了，但是另外一个链表还有剩余的节点没有进行合并的操作
if(cur1) prev->next=cur1;
if(cur2) prev->next=cur2;
return head.next;
}
};56.K 个一组翻转链表
题目链接
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1：
输入： head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
输入： head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
我们需要先求出逆序多少组
重复n次，长度为k的链表即可 对于下面的链表我们是先需要求出多少组要逆序的，最后一段链表小于k是不需要进行逆序操作的
那么我们遍历链表，求出链表的节点个数n，然后n/3就可以得出我们的需要逆序的组数了
逆序我们使用头插法 长度为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
{
public:
ListNode* reverseKGroup(ListNode* head, int k)
{
//1.先求出需要逆序多少组
int n=0;
ListNode*cur =head;
while(cur)
{
cur=cur->next;
n++;//统计链表节点的个数
}
n/=k;//n这里就是需要逆序多少组了
//2.重复n次，长度为K的链表的逆序就行了
ListNode*newHead= new ListNode(0);//先创建一个哨兵位
ListNode*prev=newHead;//每次逆序需要头插的节点，头插在这个prev后面
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;//让我们当前节点的next指向我们的prev的next的位置
prev->next=cur;
cur=next;
}
//1->2->3->4->5
//2->1->4->3
//我们先将1头插到我们的prev的下个节点，然后进行2的头插操作
//这一段链表头插完毕了，那么我们的头插的点就需要更新了
prev=tmp;//我们需要将我们的头插点定位到我们的开始位置
//我们现在将1和2这段头插好了，那么开始3和4这段头插了，那么我们直接让这一段接在1后面头插就行了
//这就是为什么我们在循环开始将我们的当前的位置进行保存
}
//当循环结束之后，此时的cur里面存的就是不需要逆置的链表，所以这里我们将剩下的链表接上就行了
prev->next=cur;
//接下来返回最后的结果
cur=newHead->next;
delete newHead;
return cur;
}
};腾讯云开发者
