C++优选算法九链表

一、常用技巧

画图！直观形象，便于理解。
引入虚拟“头”结点。
不吝啬空间。
快慢双指针：

判环
找链表中环的入口
找链表中倒数第n个结点

二、常用操作

创建一个新结点
尾插
头插

三、示例题目

1.两数相加. - 力扣（LeetCode）

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：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]

解法(模拟):
算法思路:
两个链表都是逆序存储数字的，即两个链表的个位数、十位数等都已经对应，可以直接相加。在相加过程中，我们要注意是否产生进位，产生进位时需要将进位和链表数字一同相加。如果产生进位的位置在链表尾部，即答案位数比原链表位数长一位，还需要再 new 一个结点储存最高位。

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int ret=0;ListNode *head=new ListNode(0);//创建一个虚拟头结点ListNode*phead=head;while(l1&&l2){ret+=l1->val;ret+=l2->val;ListNode*node=new ListNode(ret%10);ret/=10;phead->next=node;phead=node;l1=l1->next;l2=l2->next;}while(l1)//处理剩下的结点{ret+=l1->val;ListNode*node=new ListNode(ret%10);phead->next=node;phead=node;ret/=10;l1=l1->next;}while(l2)//处理剩下的结点{ret+=l2->val;ListNode*node=new ListNode(ret%10);phead->next=node;phead=node;ret/=10;l2=l2->next;}if(ret!=0){phead->next=new ListNode(ret);}return head->next;}
};

2.两两交换链表中的结点. - 力扣（LeetCode）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

解法（模拟）

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.重排链表. - 力扣（LeetCode）

给定一个单链表 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]

解法:
算法思路:画图画图画图，重要的事情说三遍~

找中间节点;（快慢双指针）
中间部分往后的逆序;（双/三指针、头插法）
合并两个链表。（双指针）

class Solution {
public:void reorderList(ListNode* head){if (head == nullptr || head->next == nullptr)return;//快慢指针找中间节点ListNode* slow = head, * fast = head;while (fast != nullptr&&fast->next!=nullptr){slow = slow->next;fast = fast->next->next;}ListNode* pphead = head;while (pphead->next != slow){pphead = pphead->next;}pphead->next = nullptr;//逆序后半部分ListNode* newhead = new ListNode(0);ListNode* node = newhead;ListNode* s = slow;ListNode* ss = slow;while (s){s = s->next;slow->next = newhead;newhead = slow;slow = s;}delete(node);node = nullptr;ss->next = nullptr;//合并链表ListNode* phead = new ListNode(0);ListNode* newnode = phead;while (head && newhead){phead->next = head;head = head->next;phead = phead->next;phead->next = newhead;phead = phead->next;newhead = newhead->next;}head = newnode->next;delete(newnode);}
};

4.合并K个升序链表. - 力扣（LeetCode）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 = [[]]
输出：[]

解法一(利用堆)
算法思路:
合并两个有序链表是比较简单的，就是用双指针依次比较链表 1、链表 2 未排序的最小元素，选择更小的那一个加入有序的答案链表中。

合并 K 个升序链表时，我们依旧可以选择 K 个链表中，头结点值最小的那一个。那么如何快速的得到头结点最小的是哪一个呢？用堆这个数据结构就好，我们可以把所有的头结点放进一个小根堆中，这样就能快速的找到每次 K 个链表中，最小的元素是哪个。

class Solution {
public:class compere{public:bool operator()(ListNode* n1, ListNode* n2){return n1->val > n2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {int count=0;for(auto e:lists){if(e==nullptr)count++;}if(count==lists.size())return nullptr;//创建一个小根堆，自己设置比较规则，按结点中的值进行比较priority_queue<ListNode*, vector<ListNode*>, compere> myHeap;ListNode* head = new ListNode(0);ListNode* phead = head;//让所有头结点进入小根堆for (auto e : lists){if(e!=nullptr)myHeap.push(e);}//合并K个有序链表while (!myHeap.empty()){ListNode* node = myHeap.top();phead->next = node;phead = node;myHeap.pop();node = node->next;if (node == nullptr)continue;myHeap.push(node);}return head->next;}
};

解法二(递归/分治)
算法思路:
逐一比较时，答案链表越来越长，每个跟它合并的小链表的元素都需要比较很多次才可以成功排序。比如，我们有8个链表，每个链表长为 100。逐一合并时，我们合并链表的长度分别为(0,100),(100,100),(200,100),(300,100),(400,100),(500,100),(600,100),(700,100)。所有链表的总长度共计 3600。如果尽可能让长度相同的链表进行两两合并呢?这时合并链表的长度分别是(100,100)x4,(200,200)x2,(400,400)，共计 2400。比上一种的计算量整整少了 1/3。迭代的做法代码细节会稍多一些，这里给出递归的实现，代码相对洁，不易写错。
算法流程:
1.特判，如果题目给出空链表，无需合并，直接返回；
2.返回递归结果。
递归函数设计:

递归出口: 如果当前要合并的链表编号范围左右值相等，无需合并，直接返回当前链表;
应用二分思想，等额划分左右两段需要合并的链表，使这两段合并后的长度尽可能相等；
对左右两段分别递归，合并 [ l , r ] 范围内的链表；

再调用 mergeTwoLists 函数进行合并(就是合并两个有序链表)。

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists,0,lists.size()-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;//2.递归处理左右区间ListNode*l1=merge(lists,left,mid);ListNode*l2=merge(lists,mid+1,right);//合并两个有序链表return mergeTowList(l1,l2);}ListNode*mergeTowList(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;}};

5.K个一组翻转链表. - 力扣（LeetCode）

给你链表的头节点 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]

解法(模拟)
算法思路:
本题的目标非常清晰易懂，不涉及复杂的算法，只是实现过程中需要考虑的细节比较多。

我们可以把链表按 K 个为一组进行分组，组内进行反转，并且记录反转后的头尾结点，使其可以和前、后连接起来。思路比较简单，但是实现起来是比较复杂的。

我们可以先求出一共需要逆序多少组(假设逆序 n 组)，然后重复 n 次长度为 k 的链表的逆序即可。

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {//1.求出需要逆序多少组ListNode*phead=head;int n=0;while(phead){n++;phead=phead->next;}n=n/k;//2.重复n次：长度为K的链表的逆序即可ListNode*node=new ListNode(0);ListNode*prev=node;ListNode*tmp=nullptr;ListNode*next=nullptr;for(int i=0;i<n;i++){tmp=head;for(int j=0;j<k;j++){next=head->next;head->next=prev->next;prev->next=head;head=next;}prev=tmp;}//3.把不需要翻转的链接上if(head){tmp->next=head;}ListNode*newnode=node->next;delete node;node=nullptr;return newnode;}
};