——链表——

目录

1 两数相加

2 两两交换链表中的节点

3 重排链表

4 合并 K 个升序链表

5 K 个一组翻转链表

---

链表类题目我们在学习数据结构的时候已经接触过许多，相信大家都已经有一定的基础，如果有所遗忘，可以在我的C语言数据结构专栏中找到链表章节进行阅读。链表类问题其实一般都不难，一般的操作就是头插，逆序等，大多数情况下，new一个哨兵头节点会让链表的操作更简单，简化边界条件的特殊处理。

1 两数相加

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

题目解析：本题给定我们两个数字，数字的每一位使用链表逆序存储，要求我们求出两个数字的和，用链表逆序表示结果的每一位。

本题其实已经给的是逆序之后的每一位数字，有的时候题目给定数字是按照从高到低的顺序存储，这种情况下我们可能还需要先逆序再进行运算。

本题其实没什么难度，从低到高计算每一位的相加结果以及进位就行了，返回值我们构建一个链表返回，可以先new一个哨兵头节点，这样一来我们就不需要考虑reshead为空的时候。

代码如下：

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode(); //哨兵头节点//从低到高不断计算每一位的结果以及进位，尾插到结果auto tail = head;int carry = 0 ; //表示进位while(l1 && l2){int x = l1->val + l2->val + carry;carry = x / 10;x %= 10;tail->next = new ListNode(x);tail = tail->next;l1 = l1->next;l2 = l2->next;}//最后还剩下一个链表，也有可能一样长，但是最终还有进位while(l1){int x = l1->val + carry;carry = x / 10;x %= 10;tail->next = new ListNode(x);tail = tail->next;l1 = l1->next;}while(l2){int x = l2->val + carry;carry = x / 10;x %= 10;tail->next = new ListNode(x);tail = tail->next;l2 = l2->next;}if(carry != 0) tail->next = new ListNode(carry);auto res = head->next;delete head;  //释放哨兵头节点return res;}
};

2 两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

题目解析：题目要求我们将链表从前往后分为两两一组，然后将每一组的两个节点进行交换。

那么每一组节点再进行交换的时候，我们需要考虑四个节点，前一个节点，本组的第一个节点，本组的第二个节点，后一个节点，对于这种关系比较复杂的，我们最好不要吝啬空间，直接使用变量将这几个节点指针都存储起来，防止节点丢失。

而交换的时候，无非就是一次越过两个节点进行交换，为了统一操作，我们也可以使用一个哨兵头节点。

代码如下：

class Solution {
public:ListNode* swapPairs(ListNode* head) {//下面的代码都是基于会进至少一次循环，特殊情况就是一次循环不进，不需要交换if(!head || !head->next)return head;ListNode* newhead = new ListNode; //哨兵头节点auto prev = newhead ; //用于标识本组节点的上一个节点while(head && head->next){ //最后只剩一个节点的时候也不需要交换了auto first = head , second = head->next , next = head->next->next;  //本组的第一个节点，第二个节点，后面一个节点prev->next = second , second->next = first , first->next = next;prev = first; //更新prevhead = next; //下一组节点}auto res = newhead->next;delete newhead;return res;}
};

3 重排链表

143. 重排链表 - 力扣（LeetCode）

题目解析：题目给定一段链表，要求我们按照第一个->倒数第一个->第二个->倒数第二个... 来进行重排。

重排后的链表其实我们可以看待：原始链表与原始链表的逆序链表交替插入组成的新链表，当然由于我们不需要重复节点，那么我们可以这样做：

1 将链表分成两半，前半段不变，后半段进行逆序。（如果节点个数为奇数个，那么最中间的节点划分给前半段和后半段都行，最终都会排在结果的最后面）

2 将后半段链表进行逆序

3 将两个链表进行交替插入到结果中。

而要将链表分为两半，我们需要找到链表的中间节点，可以使用快慢双指针算法来查找，fast指针一次向后移动两个节点，slow指针一次向后移动一个节点，那么最终fast == null 的时候，slow就指向中心节点，此时结点个数为奇数个。如果fast->next == null ，那么节点总个数为偶数个 ，此时我们也需要将slow向后移一个节点，使slow指向后半段的第一个节点。

但是其实我们不需要纠结fast==null还是fast->next==null，不管是奇数个节点还是偶数个节点，当循环退出的时候，我们都可以将slow所在的节点看成是前半段链表的最后一个节点（如果是奇数个，那么我们让前半段链表多一个节点）。

代码如下：

class Solution {
public:void reorderList(ListNode* head) {if (!head)return ;auto fast = head, slow = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;}auto l1 = head, l2 = slow->next;slow->next = nullptr;// 然后将后半段节点进行逆序ListNode* h2 = nullptr;// 逆置链表就是不断头插while (l2) {auto next = l2->next;if (!h2)h2 = l2, h2->next = nullptr;else {l2->next = h2;h2 = l2;}l2 = next;}l2 = h2;auto newhead = new ListNode , tail = newhead;//交叉组成新链表返回while(l1){tail->next = l1;l1 = l1->next;tail = tail->next;if(l2){   //结点个数为奇数的时候，l1会多一个节点，此时l2为空tail->next = l2;l2 = l2->next;tail = tail->next;}}// head = newhead->next;delete newhead;}
};

4 合并 K 个升序链表

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

题目解析：本题给定多个升序链表，要求我们将这些升序链表合并返回新的升序链表。

题目主要的思想其实就是一个归并排序，只不过是对链表进行操作。

如果按照正常的归并排序来做的话，我们每一次都需要遍历这K个链表的头节点，来找出最小值，同时还需要判断对应的链表已经走到结尾，如果k比较大，时间复杂度比较高，不推荐这样做。

我们每一次选一个节点的时候，都需要在k个链表中选出最小的头节点，那么我们其实可以使用一个堆来做，堆里面保存 pair<int,ListNode*> 的键值对，每次取出最小的头节点之后，我们再将这个头节点连接到结果链表的同时，将本节点的下一个节点入堆，继续进行选最小的节点，这样一来选数的时间复杂度就是O(logK)，同时我们如果本节点的下一个节点为空，我们就不需要将其放入堆中，也省去了考虑空节点的情况。

代码如下：

class Solution {
public:typedef pair<int,ListNode*> PIL;class mygreater{public:bool operator()(const PIL& p1 , const PIL&p2){return p1.first > p2.first;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<PIL,vector<PIL>,mygreater> pq;  //使用pq的时候，如果要传自定义的比较规则，第二个模板参数需要传存储的容器，可以使用list或者vector，一般使用vectorfor(auto h : lists) if(h) pq.emplace(h->val,h);auto head = new ListNode , tail = head;while(!pq.empty()){PIL p = pq.top();pq.pop();tail->next = p.second;if(p.second->next) pq.emplace(p.second->next->val , p.second->next);tail = tail->next;}auto res = head->next;delete head;return res;}
};

5 K 个一组翻转链表

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

题目解析：本题要求我们将链表分成k个一组，将每一组节点进行逆置，最后一组的节点个数如果不足k个，那么最后一组不需要翻转。

本题最简单的做法就是按照题目意思，我们先将前k个节点拿出来，将其进行逆置，然后保存逆置之后的尾节点，然后再去找下一组k个节点进行逆置，直到最终找不出k个节点。

代码如下：

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {auto newhead = new ListNode , tail = newhead;while(head){//找出k个节点auto end = head , cur = head;int m = k;while(end && --m)end = end->next;  //注意是--m，只需要向后走k-1次就行了，这时候end是本组的最后一个节点if(m){tail->next = head;break ; //m>0说明不足k个节点了}head = end->next;end->next = nullptr;//对head开始的链表进行逆置ListNode* h = nullptr;end = cur;while(end){auto next = end->next;if(!h) h = end , end->next= nullptr;else end->next = h , h = end;end = next;}//逆置之后的链表保存在h->nexttail->next = h;//然后更新tail，逆置之后，tail其实就是本组节点的第一个节点tail = cur;}auto res = newhead->next;delete newhead;return res;}
}; 

还有一种思路就是：

1、我们先求出链表的总长度，求出一共需要翻转多少组链表

2、进行多组k个节点的链表反转。

这种做法代码可能会更简单，但是思路跟上面类似。

总结

链表类型的题目难度一般不大，一般的操作就是头插尾插，真正考察的其实是在头插尾插的过程中我们不能丢失节点，而为了防止节点丢失，最好的方法就是多使用变量来保存有关节点。