【基础算法总结】链表篇

embedded/2024/10/18 12:21:10/

目录

一， 链表常用技巧和操作总结

有关链表的算法题也是一类常见并且经典的题型，这些题要使用数据结构中我们手搓的链表结构，也要使用STL中的 list 容器。

下面是几点常用操作的总结：
(1) 善于画图。
(2) 引入虚拟头结点。
方便处理边界情况，就是当没节点第一次头插或尾插的时候的那个判断，引入虚拟头结点就可以避免这个判断(写成 ptail = newHead)。
(3) 不要吝啬空间，大胆定义变量。
(4) 快慢双指针的使用。
主要应用是判环，找链表中环的入口，找链表中倒数第 n 个节点。
(5) 解决链表类的题，一般是：创建一个新节点，尾插操作，头插操作。

我们在学习数据结构时也做过许多有关链表类的经典题目，请浏览：【C/数据结构与算法】10道链表经典OJ。
里面的一些题目与本篇文章的题目也是有关联的，这篇文章算是进阶篇。

二，算法原理和代码实现

2.两数相加

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理：

这道题是一道简单的模拟题，模拟两数相加即可。
定义两个指针 cur1和cur2用于遍历两个链表，再定义一个整数 t 用于进位。用 t 和每个节点的值相加，取出 t 的个位创建新节点。
在这里插入图片描述

细节问题：

(1) 这里要注意的细节就是链表是逆序的，其实这也是方便我们操作，因为我们可以直接从个位开始相加。
(2) 1. 循环条件：cur1 || cur2 || t
这里要或t是原因：当两个指针都走完时，t里可能还有进位，还需要尾插
(3) 要销毁哨兵位头节点

代码实现：

class Solution 
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1, *cur2 = l2;ListNode* newHead = new ListNode(), *ptail = newHead; // 虚拟头节点int t = 0; // 记录进位while(cur1 || cur2 || t){if(cur1) {t += cur1->val;cur1 = cur1->next;}if(cur2) {t += cur2->val;cur2 = cur2->next;}ListNode* newNode = new ListNode(t % 10);ptail->next = newNode;ptail = newNode;ptail->next = nullptr;t /= 10;}ListNode* pcur = newHead->next;delete newHead;return pcur;}
};

24.两两交换链表中的节点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理：

本题也是一道模拟题，重点是画图，看图写代码!!! 定义四个指针：
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/dd888c8a2f4e4bf098ccdb8d4b4c7392.png
根据交换后的链表，进行指针的修改(绿色字)，一直循环迭代。
结束条件：
(1) 偶数个节点时：
cur 已经指向空了，next 和 nnext 也无效了，此时结束循环。
在这里插入图片描述
(2) 奇数个节点时：
next 已经指向空了， nnext 无效了，此时也结束循环。
在这里插入图片描述

代码实现：

class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr) return nullptr;ListNode* newHead = new ListNode(), *prev = newHead;ListNode* cur = head, *next = cur->next;ListNode* nnext = nullptr;if(next) nnext = next->next;prev->next = cur;while(cur && next){// 交换节点prev->next = next;next->next = cur;cur->next = nnext;// 修改指针prev = cur;cur = prev->next;if(cur) next = cur->next;if(next) nnext = next->next;}ListNode* pcur = newHead->next;delete newHead;return pcur;}
};

143.重排链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理：

这道题比较有综合性，通过分析可以发现：
重排后的链表 = 合并两个链表(原链表的前半段 + 原链表的后半段逆置)。
在这里插入图片描述
所以这道题的思路是：
(1) 找到链表的中间节点
(2) 把后半部分逆序
(3) 合并两个链表

代码实现：

class Solution 
{
public:// 找中间节点ListNode* FindMiddleNode(ListNode* head){ListNode* slow = head, *fast = head, *prev = head;while(fast && fast->next){prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = nullptr; // 与后半段断开return slow;}// 逆置后半部分链表ListNode* reverseList(ListNode* head){ListNode* phead = head, *ptail = nullptr;while(phead){ListNode* next = phead->next;// 头插法phead->next = ptail;ptail = phead;phead = next;}return ptail;}void reorderList(ListNode* head) {// 处理特殊情况if(head->next == nullptr || head->next->next == nullptr) return;ListNode* mNode = FindMiddleNode(head);ListNode* rNode = reverseList(mNode);// 合并两个链表ListNode* newHead = new ListNode(), *ptail = newHead;ListNode* n1 = head, *n2 = rNode;while(n1 && n2){ptail->next = n1;ptail = ptail->next;n1 = n1->next;ptail->next = n2;ptail = ptail->next;n2 = n2->next;}if(n1) ptail->next = n1;if(n2) ptail->next = n2;delete newHead;}
};

23.合并k个升序链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理：

解法1：暴力解法，利用"合并两个有序链表"的思想。先把第一个和第二个链表进行合并，得到一个新链表，再用新链表和第三个链表进行合并…。
假设有 k 个链表，每条链表的平均节点有 n 个，则时间复杂度为：n(k-1) + n(k-2) + n(k-3) + … + n --> O(n * k^2)。大概率超时。

解法2：利用优先级队列进行优化。
假设有 k 个链表，建一个大小为 k 的小根堆，把所有链表的第一个节点都扔进小根堆中，堆顶节点就是最小值，取出堆顶节点和虚拟头结点进行链接，再移到下一个节点…
合并链接+找出最小值的节点总的时间复杂度为：O(n * k * logk)。

易错/细节问题：

(1) 优先级队列的第三个模板参数不能直接写成 greater<ListNode * >，因为这样比较的是地址，要写一个仿函数!!
(2) 把链表的所有头节点都入队列时，要注意传递的链表为空的处理。

代码实现：

class Solution
{struct cmp{bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists){// 建小根堆priority_queue<ListNode*, vector<ListNode*>, cmp> pq;// 把所有头结点进小根堆for (auto l : lists)if (l) pq.push(l);// 合并k个有序链表ListNode* newhead = new ListNode(), * ptail = newhead;while (!pq.empty()){ListNode* pcur = pq.top();pq.pop();ptail->next = pcur;ptail = pcur;if (pcur->next) pq.push(pcur->next);}ListNode* ret = newhead->next;delete newhead;return ret;}
};

解法3：分治-递归
和归并分治的思想一样：
在这里插入图片描述
假设有 k 个链表，那么就有 logk 层，递归回退时每个链表的每个节点都执行 logk 次合并，每个链表的平均节点有 n 个，所以时间复杂度为：O(n * k * logk)。

易错/细节问题：

(1) 有两个递归出口：区间不存在和区间里只有一个链表。
(2) 合并两个有序链表时，链表为空的情况。

代码实现：

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];// 找中点int mid = left + (right - left) / 2;// [left, mid] [mid+1, right]// 合并左右两边ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid+1, right);// 合并两个有序链表return mergeTwoList(l1, l2);}ListNode* mergeTwoList(ListNode* l1, ListNode* l2){// 处理特殊情况if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;ListNode head; // 把虚拟节点开在栈上head.next = nullptr;ListNode* ptail = &head;while(l1 && l2){if(l1->val < l2->val){ptail->next = l1;ptail = ptail->next;l1 = l1->next;}else{ptail->next = l2;ptail = ptail->next;l2 = l2->next;}}if(l1) ptail->next = l1;if(l2) ptail->next = l2;return head.next;}
};

25.k个一组翻转链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法原理：

这也是一道模拟题，算法流程比较简单：
(1) 先求出需要逆序多少组：n。
(2) 重复 n 次，长度为 k 的链表的逆序即可 。
(3) 把不需要逆序的接上。
在这里插入图片描述

细节问题：

(1) 这里需要记录第n次头插的开始位置，每次进行新一轮逆序时都要记住该位置。
(2) 如果使用while循环，则每逆序完一组后 k 要重新赋值，不然就一直都是k==0了。

代码实现：

class Solution
{
public:ListNode* reverseKGroup(ListNode* head, int k){// 先求出要逆序多少组int n = 0;ListNode* phead = head;while (phead){phead = phead->next;n++;}n /= k;// 重复 n 次长度为 k 的链表逆序phead = head;ListNode* newhead = new ListNode(), * prev = newhead;for (int i = 0; i < n; i++){ListNode* tmp = phead; // 记录每一组的起点for (int j = 0; j < k; j++){ListNode* next = phead->next;phead->next = prev->next;prev->next = phead;phead = next;}prev = tmp;}// 把不需要翻转的接上prev->next = phead;ListNode* ret = newhead->next;delete newhead;return ret;}
};

三，算法总结

通过上面的若干道题目可以发现，大多数链表类的题目本质上是模拟题，最重要的就是画图，分清各个指针指向哪里。


http://www.ppmy.cn/embedded/124231.html

相关文章

数据结构：AVL树

数据结构：AVL树

前言 学习了普通二叉树&#xff0c;发现普通二叉树作用不大&#xff0c;于是我们学习了搜索二叉树&#xff0c;给二叉树新增了搜索、排序、去重等特性&#xff0c; 但是&#xff0c;在极端情况下搜索二叉树会退化成单边树&#xff0c;搜索的时间复杂度达到了O(N)&#xff0c;这…
阅读更多...
VRRP协议

VRRP协议

文章目录 一、什么是VRRP协议 一、什么是VRRP协议 VRRP协议是一种用于提高网络可靠性的容错协议。 VRRP协议是一种容错的主备模式的协议&#xff0c;保证当主机的下一跳路由出现故障时&#xff0c;由另一台路由器来代替出现故障的路由器进行工作&#xff0c;通过VRRP可以在网络…
阅读更多...
力扣刷题之2306.公司命名

力扣刷题之2306.公司命名

题干描述 给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下&#xff1a; 从 ideas 中选择 2 个 不同 名字&#xff0c;称为 ideaA 和 ideaB 。交换 ideaA 和 ideaB 的首字母。如果得到的两个新名字 都 不在 ideas 中&#xff0c;那么 ideaA i…
阅读更多...
Linux文件重定向文件缓冲区

Linux文件重定向文件缓冲区

目录 一、C文件接口 二、系统文件I/O 2.1认识系统文件I/O 2.2系统文件I/O 2.3系统调用和库函数 2.4open( )的返回值--文件描述符 2.5访问文件的本质 三、文件重定向 3.1认识文件重定向 3.2文件重定向的本质 3.3在shell中添加重定向功能 3.4stdout和stderr 3.5如何理…
阅读更多...
提升LLM结果：何时使用知识图谱RAG

提升LLM结果：何时使用知识图谱RAG

通过知识图谱增强 RAG 可以帮助检索&#xff0c;使系统能够更深入地挖掘数据集以提供详细的响应。 译自Boost LLM Results: When to Use Knowledge Graph RAG&#xff0c;作者 Brian Godsey。 有时&#xff0c;检索增强生成 (RAG) 系统无法深入文档集以找到所需的答案。我们可能…
阅读更多...
【预备理论知识——2】深度学习：线性代数概述

【预备理论知识——2】深度学习：线性代数概述

简单地说&#xff0c;机器学习就是做出预测。 线性代数 线性代数是数学的一个分支&#xff0c;主要研究向量空间、线性方程组、矩阵理论、线性变换、特征值和特征向量、内积空间等概念。它是现代数学的基础之一&#xff0c;并且在物理学、工程学、计算机科学、经济学等领域有着…
阅读更多...
【rCore OS 开源操作系统】Rust 异常处理

【rCore OS 开源操作系统】Rust 异常处理

【rCore OS 开源操作系统】Rust 异常处理 前言 虽然人还在旅游ing&#xff0c;但是学习不能停止&#xff0c;所以还是写点博客记录下。 对于 Rust 的异常处理&#xff0c;我的感受是&#xff1a;晦涩难懂&#xff0c;繁琐难记。 但是没办法&#xff0c;正如一位故人所说的&…
阅读更多...
【GAN 图像生成】

【GAN 图像生成】

理论知识学习&#xff1a; PART 1&#xff1a; 生成对抗网络GAN 深度学习模型&#xff0c;用于生成数据 对抗式训练&#xff0c;生成器v判别器 DCGAN>WGAN>StyleGAN技术不断进化 GAN在艺术创作。数据增强领域应用越来越广泛 应用&#xff1a; GAN在图像合成&#x…
阅读更多...
最新文章

Copyright @ 2022~2023