算法_链表专题---持续更新

前言

本文将记录leetcode链表算法题解，包含题目有：两数相加、两两交换链表中的节点、重排链表、合并K个升序链表、K个一组翻转链表

两数相加

https://leetcode.cn/problems/add-two-numbers/

题目要求

题目解析

已经给你两个逆序的链表，如果不是给逆序的，还需要自己逆序一下，因为加法是从低位到高位相加的，重点是低位到高位的过程中可能会有进位，关键的就是这个进位，逆序后（就相当于正常顺序的低位开始相加，因为我们的逻辑就是从链表的头部开始加，依次遍历向后走），链表从头部依次相加向后走，有进位进位即可 题目给的两个链表是已经逆序过的，包括最后的要求结果也是逆序的，不需要做任何修改

代码如下

/*** 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* newhead = new ListNode(0);   //新链表ListNode* tail = newhead;    //尾节点ListNode * cur1 = l1;ListNode * cur2 = l2;int ret = 0;    //进位//注意这种情况：当两个链表节点都为空时，进位不为空，需要进位while(cur1 || cur2 || ret){//第一个链表中节点不为空if(cur1){ret += cur1->val;cur1 = cur1->next;}//第二个链表中节点不为空if(cur2){ret += cur2->val;cur2 = cur2->next;}tail->next = new ListNode(ret % 10);tail = tail->next;ret /= 10;  //进位}//释放new出的内存tail = newhead->next;delete newhead;return tail;}
};

两两交换链表中的结点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

题目要求

题目解析

题目要求两两交换相邻的节点，且不能修改节点的值，我们只需要改变节点的next指针的指向即可，为了方便两两交换我们引入一个哨兵位（当交换1、2节点时，只需要让哨兵位->next指向2这个节点....省略，这样方便很多） 要求是两两交换，实际上会影响到四个节点，哨兵位、cur、next、nnext，因为交换节点的时候，我们需要修改对应的next指向

当需要进行下一次两两交换的时候，先把prev向后移动两位
因为进行3、4节点交换的时候，1节点的next会指向4节点了
因此我们需要一个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* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);    //虚拟头节点dummyHead->next = head;ListNode* prev = dummyHead;//cur、next不为空while(prev->next !=nullptr && prev->next->next != nullptr){ListNode* cur = prev->next;ListNode* next = cur->next;ListNode* nnext = next->next;//两两交换（cur、next）prev->next = next;next->next = cur;cur->next = nnext;//向后移动prev = prev->next->next;}return dummyHead->next;}
};

重排链表

https://leetcode.cn/problems/reorder-list/description/

题目要求

题目解析

这道题本质上是一道模拟题，根据题目以及示例模拟出设计过程，这道题比较综合，会运用到链表的中间节点、反转链表这两道基础题的方法
模拟：
找到中间节点，分割成两个链表，并将后面一个链表反转
按照先添加第一个链表的第一个节点，再添加第二个链表的第一个节点，先添加第一个链表的第二个节点
再添加第二个链表的第二个节点的顺序以此类推


1、首先利用快慢指针找到中间位置（快指针一次前进两步，慢指针一步，这样快指针每次都是慢指针的二倍，当快指针走到链表结尾时，慢指针就走到中间位置）
2、链表分割，这里非常重要，我第一次做的时候就忘记将链表断开了，记得将第一个链表的结尾节点的next置空，这里的逻辑是将slow->next位置开始作为第二个链表（不包含当前slow指针指向的节点）
当然也可以用包含slow以及后面的所有节点作为第二个链表
3、链表反转，也就是逆序，不断地将节点头插到新空间即可
4、按照模拟顺序依次重组链表
由于将slow->next位置开始作为第二个链表，所以无论是奇数个还是偶数个
节点，都是第一个链表长于第二个链表，因此当重组的时候，循环条件是第一个链表节点不为空，这样当第一个链表节点出现为空的时候，第二个链表肯定早早就结束了，就可以重组所有节点了
以下是使用快慢双指针找中间节点（slow指针指向的位置）的奇数以及偶数讨论

代码如下

/*** 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) {//当链表节点数为1或2时，直接返回if(head->next == nullptr || head->next->next == nullptr) return;//利用快慢指针找到中间位置ListNode* fast = head;ListNode* slow = head;//链表中的节点为奇数/偶数while(fast&&fast->next){fast = fast->next->next;slow = slow->next;}//分割断开为两个链表ListNode* cur = slow->next;slow->next = nullptr;//翻转第二个链表ListNode* head2 = new ListNode(0);ListNode* curr = cur->next; //保存下一个节点while(cur){            curr = cur->next;cur->next = head2->next;head2->next = cur;cur = curr;}ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode* cur1 = head;ListNode* cur2 = head2->next;//分割时按照slow->next慢指针的后一个节点进行分割，所以第一个链表是最长的，第一个链表遍历完毕就结束while(cur1){prev->next = cur1;prev = prev->next;cur1 = cur1->next;if(cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}head = ret;}
};

合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

题目要求

题目解析

合并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://C++标准库不提供对自定义数据类型的排序规则（ListNode）,所以需要重载operator()struct cmp{bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {//创建一个小根堆（根据给定的比较规则自动对元素进行排序）priority_queue<ListNode*, vector<ListNode*>, cmp> heap;//将所有链表的头节点先添加入小根堆中for(auto l : lists){//链表可能为空if(l)heap.push(l);}ListNode* ret = new ListNode(0);    //虚拟头节点ListNode* prev = ret;while(!heap.empty()){ListNode* t = heap.top();prev->next = t;heap.pop();prev = prev->next;  //更新if(t->next) heap.push(t->next); //将每个链表都向后推进}prev = ret->next;delete ret;return prev;}
};

K个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

题目要求

题目解析

这道题不需要什么技巧，只需要把过程模拟出来就好，首先读题，k个节点为一组，并按照一组为单位进行逆序，那么我们需要先将总节点的个数算出，再计算出一共需要逆序多少组，两个循环就可以搞定

for(逆序多少组)
{for(每一组需要逆序多少个节点) {}
}
最后将剩下不需要逆序的节点接在最后面

逆序逻辑


注意
当逆序到下一组的时候，我们是需要提前保存第一组逆序的第一个节点的，ListNode* tmp = cur，因为第一个
节点逆序后一定是在第一组的最后一个位置（紧接第二组）

代码如下

/*** 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) {//遍历链表计算总节点数ListNode* num = head;int n = 0;  //总节点数while(num){num = num->next;n++;}int group = n/k;ListNode* dummyHead = new ListNode(0);  //虚拟头节点ListNode* prev = dummyHead; //cur的前一个节点ListNode* cur = head;    //当前节点for(int i = 0; i < group; 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; //更新下一组逆序的前一个位置}//加上不需逆序的节点if(cur) prev->next = cur;//释放，防止内存泄漏prev = dummyHead->next;delete dummyHead;return prev;}
};