> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握链表算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
- 画图，一定要画图，只有画好图才能直观形象便于我们理解。
- 引入虚拟"头"结点。
- 不要吝啬空间，大胆去定义变量。
🌙topic-->1
题目链接：1. 两数相加
题目分析：
给一个非空的链表，表示的是两个非负的整数，它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字，然后将两个数字相加，并以相同形式返回一个表示和的链表。
算法原理：
- 解法：模拟两数相加的过程即可
图解：
细节处理：
- 判端循环结束标志。
- 可能存在两个链表长短不一。
- 不要忘记释放空间。
代码演示：
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 = t + cur1->val; cur1 = cur1->next;// 指针需要移动 } // 再加上第二个链表 if(cur2) { t = t + cur2->val; cur2 = cur2->next;// 指针需要移动 } // 开始进位 prev->next = new ListNode(t % 10); prev = prev->next; t = t/10; } prev = newhead->next; // 回到最初位置 delete newhead;// 释放空间 return prev; } };
🌙topic-->2
题目链接：2. 两两交换链表中的节点
题目分析：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题。
算法原理：
- 解法一：采用递归（有兴趣大家自己可以上手写写）
- 解法二：循环+迭代（模拟）
图解：
细节处理：
- 判断链表边界情况。
- 循环结束标志。
- 不要忘记释放空间。
代码演示：
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; } };
🌙topic-->3
题目链接：3. 重排链表
题目分析：
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
算法原理：
- 解法：模拟
图解：
无
细节处理：
- 判断链表边界情况。
代码演示：
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; } // 2. 把 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; } // 3. 合并两个链表 - 双指针 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; prev = prev->next; cur2 = cur2->next; } } delete head2; delete ret; } };
🌙topic-->4
题目链接：4. 合并 K 个升序链表
题目分析：
给你一个链表数组，每个链表都已经按升序排列，请你将所有链表合并到一个升序链表中，返回合并后的链表。
算法原理：
- 解法：递归+分治
图解：
代码演示：
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; // [left, mid] [mid + 1, right] // 2. 递归处理左右区间 ListNode* l1 = merge(lists, left, mid); ListNode* l2 = merge(lists, mid + 1, right); // 3. 合并两个有序链表 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; } };
🌙topic-->5
题目链接：5. K 个一组翻转链表
题目分析：
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
算法原理：
- 解法：模拟
图解：
代码演示：
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // 1. 先求出需要逆序多少组 int n = 0; ListNode* cur = head; while(cur) { cur = cur->next; n++; } n /= k; // 2. 重复 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; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
