C++ 链表OJ

news/2024/4/24 17:34:40/文章来源:https://blog.csdn.net/m0_73800602/article/details/136458329

目录

1、2. 两数相加

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

3、143. 重排链表

4、23. 合并 K 个升序链表

5、25. K 个一组翻转链表


解决链表题目常用方法:

1、画图
2、引入虚拟"头”结点

  • 便于处理边界情况
  • 方便我们对链表操作

3、大胆定义变量,减少连接节点时出现错误。

4、快慢双指针

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

1、2. 两数相加

 思路:模拟相加,注意进位问题。

/*** 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* cur1=l1,*cur2=l2;ListNode* cur=newhead;int c=0;//进位while(cur1||cur2||c){if(cur1){c+=cur1->val;cur1=cur1->next;}if(cur2){c+=cur2->val;cur2=cur2->next;}cur->next=new ListNode(c%10);cur=cur->next;c/=10;}cur=newhead->next;delete newhead;return cur;}
};

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

 思路:循环、迭代(模拟)。定义一个带有虚拟头结点的链表统计结果,接着定义出包括虚拟头结点在内和它后三个节点方便直接插入新链表。

/*** 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) {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 = prev->next;if (cur)next = cur->next;if (next)nnext = next->next;}cur = newHead->next;delete newHead;return cur;}
};
  • 首先创建一个新的头节点newHead,其值为0,并将其指向原链表的头节点head
  • 使用指针prev指向newHead,指针cur指向prev的下一个节点(即原链表的头节点),指针next指向cur的下一个节点,指针nnext指向next的下一个节点。
  • 进入循环,条件是curnext都不为空。在循环中:
    • prevnext指针指向next,实现交换相邻节点。
    • nextnext指针指向cur,完成节点交换。
    • curnext指针指向nnext,恢复链表连接。
    • 更新prevcurcurprev的下一个节点,nextcur的下一个节点,nnextnext的下一个节点。
  • 循环结束后,重新定位cur指向新链表的头部,即newHead的下一个节点。
  • 删除创建的头节点newHead,并返回交换后链表的头节点cur

3、143. 重排链表

 思路:快慢双指针找到中间节点,逆序后半部分,利用双指针合并两个链表。

/*** 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) {if (head == nullptr || head->next == nullptr ||head->next->next == nullptr) {return;}ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}ListNode* rhead = new ListNode(0);ListNode* cur = slow->next;//逆序不要中间节点slow->next = nullptr;//分离逆序部分while (cur) {ListNode* next = cur->next;cur->next = rhead->next;rhead->next = cur;cur = next;}ListNode *cur1 = head, *cur2 = rhead->next;ListNode* ret = new ListNode(0);ListNode* prev = ret;while (cur1) {prev->next = cur1;cur1 = cur1->next;prev = prev->next;if (cur2) {prev->next = cur2;cur2 = cur2->next;prev = prev->next;}}delete rhead;delete ret;}
};

4、23. 合并 K 个升序链表

 思路:把所有的头结点放进⼀个⼩根堆(使用优先级队列实现)中,这样就能快速的找到每次 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:struct cmp {bool operator()(const ListNode* a, const ListNode* b) {return a->val > b->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();heap.pop();prev->next = t;prev = t;if (t->next)heap.push(t->next);}prev = ret->next;delete ret;return prev;}
};
  1. 定义一个比较结构体cmp,用于比较两个节点的值大小,确保优先级队列是一个最小堆。
  2. 遍历输入的链表数组lists,将每个链表的头节点(如果不为空)加入到优先级队列heap中。
  3. 创建一个哑节点ret,它将作为返回的链表的头节点的前驱,用于简化链表操作。同时,使用一个指针prev来跟踪当前链表的最后一个节点。
  4. heap不为空时,循环执行以下操作:
    • heap中取出最小值节点t(即优先级队列的顶部元素),这是当前所有链表头节点中值最小的节点。
    • prevnext指向t,将t接入到当前构建的链表中。
    • 更新prev指向t,即将prev移动到链表的最末端。
    • 如果t还有下一个节点(t->next不为空),则将这个下一个节点加入到heap中,以便继续参与后续的比较和选择过程。
  5. 循环结束后,所有输入的链表已经完全合并到了由ret->next开始的链表中。
  6. 在返回结果之前,首先保存ret->next到一个临时变量prev(这里重新使用prev变量来简化代码,其实是返回链表的头节点),然后删除哑节点ret
  7. 返回prev,即合并后的链表的头节点。

思路二:递归/分治 

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right) {int mid = left + right >> 1;if (left > right)return nullptr;if (left == right)return lists[left]; // 只有一个链表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;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、25. K 个一组翻转链表

 思路:先求出需要逆序的组数n,重复n次长度为k的链表逆序,通过头插到新链表实现逆序,每头插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:ListNode* reverseKGroup(ListNode* head, int k) {int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997386.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024-3-7 市场分歧视角

昨天安奈儿市场带领市场情绪一致&#xff0c;新型工业化方向独占鳌头&#xff0c;日内高潮节点尾盘老龙 克来机电涨停&#xff0c;昨晚很多老师在YY老龙是不是要二波了&#xff0c;呵呵。 今天市场分歧从竞价就开始了&#xff0c;隔夜单我记忆中 天奇股份88亿&#xff0c;上海…

python71-Python的函数入门,定义函数和调用函数

在使用函数之前必须先定义函数&#xff0c;定义函数的语法格式如下&#xff1a; def 函数名(形参列表)://由零条到多条可执行语句组成的函数[return [返回值]] Python声明函数必须使用def关键字&#xff0c;对函数语法格式的详细说明如下。 1&#xff09;函数名:从语法角度来…

力扣--从前序与中序遍历序列构造二叉树

题目&#xff1a; 思想&#xff1a; 首先先序遍历能确定根节点的值&#xff0c;此时查看该值在中序遍历中的位置&#xff08;如果索引为i&#xff09;&#xff0c;那么i左侧为左子树&#xff0c;i 右侧为右子树。从中序数组中即可看出左子树结点个数为 i&#xff0c;右子树节点…

Pytorch学习 day06(torchvision中的datasets、dataloader)

torchvision的datasets 使用torchvision提供的数据集API&#xff0c;比较方便&#xff0c;如果在pycharm中下载很慢&#xff0c;可以URL链接到迅雷中进行下载&#xff08;有些URL链接在源码里&#xff09;代码如下&#xff1a; import torchvision # 导入 torchvision 库 # …

线程池不香了? 结构化并发才是王道!

我们先定义获取用户信息任务&#xff1a; 再定义获取订单信息任务&#xff1a; 然后再构造线程池并执行任务&#xff1a; 输出结果为&#xff1a; 看上去一切都刚刚好&#xff0c;但是&#xff0c;如果获取订单信息时出错了&#xff0c;此时会是什么现象呢&#xff1f;修改获取…

PoC免写攻略

在网络安全领域&#xff0c;PoC&#xff08;Proof of Concept&#xff09;起着重要的作用&#xff0c;并且在安全研究、漏洞发现和漏洞利用等方面具有重要的地位。攻击方视角下&#xff0c;常常需要围绕 PoC 做的大量的工作。常常需要从手动测试开始编写 PoC&#xff0c;再到实…

SAP - 采购价格确定 ③ 抬头条件和组条件

抬头条件和组条件 当我们创建一个具有多个行项目的采购订单时,我们经常需要条件可以应用到所有的行项目中。相应的,条件也可以应用到特定的行项目。在R/3系统中,条件可以涉及采购凭证的单个行项目(项目条件),多个行项目(组条件)或所有的行项目(抬头条件)。 一些标准…

计算机/大数据毕业设计-基于Python的动漫数据分析可视化系统的设计与实现

基于Python的动漫数据分析可视化系统的设计与实现 设计爬虫程序爬取哔哩哔哩动漫数据信息 后端使用flask框架&#xff0c;数据库使用Mysql8.0&#xff0c;可视化使用echarts 部分代码如下&#xff1a; # 保存所有动漫信息 all_anime_infos [] # 保存到文件中 file_writer …

讨论:5万官网是建站界的劳斯莱斯了吧,到了软件开发领域呢?

如题&#xff0c;所以赛道选择很重要&#xff0c;当然难度系数也不一样。能花5万元做官网的&#xff0c;凤毛麟角&#xff0c;如果是做软件开发&#xff0c;5万元顶多算个起步价&#xff0c;老铁们&#xff0c;是这样吗&#xff1f;

Openwrt(IstoreOS)安装iventoy

背景 目前家里有两台不用的旧主机&#xff0c;平时没事在家里折腾这两台机器。经常换装各种系统。最早是将镜像刷入u盘作为启动盘&#xff0c;这样需要重复装系统就特别麻烦。后来用了ventoy以后一个U盘可以放多个系统镜像&#xff0c;还能做口袋系统&#xff08;SystemToGo&a…

安卓手机如何使用JuiceSSH实现公网远程连接本地Linux服务器

文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …

别再找了,关于免费SSL证书都在这里

免费SSL证书的优点&#xff1a; 成本效益&#xff1a;免费SSL证书可以帮助网站所有者节省资金&#xff0c;特别是对于初创公司或个人网站来说&#xff0c;这是一个很大的优势。提高信任度&#xff1a;通过使用SSL证书&#xff0c;网站可以向访问者展示其对安全性的承诺&#x…

2024/3/7—2575. 找出字符串的可整除数组

代码实现&#xff1a; int* divisibilityArray(char *word, int m, int *returnSize) {int n strlen(word);int *res (int*)malloc(sizeof(int) * n);long cur 0;for (int i 0; i < n; i) {cur (cur * 10 (word[i] - 0)) % m;res[i] (cur 0) ? 1 : 0;}*returnSize …

1-安装rabbitmq

rabbitmq官网&#xff1a; https://www.rabbitmq.com/docs/download 本机环境&#xff1a;mac&#xff0c;使用orbstack提供的docker 使用docker部署rabbitmq docker run -it --rm --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management 然后报错&#xf…

基于STC系列单片机实现PNP型三极管S8550驱动共阳数码管或NPN型三极管S8050驱动共阴数码管功能

Digitron.c #include "Digitron.h" //#include "Key.h" #define uchar unsigned char//自定义无符号字符型为uchar #define uint unsigned int//自定义无符号整数型为uint //uchar code DigitronBitCodeArray[] {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x8…

机器学习-面经(part8、贝叶斯和其他知识点)

机器学习面经其他系列 机器学习面经系列的其他部分如下所示&#xff1a; 机器学习-面经(part1)-初步说明 机器学习-面经(part2)-交叉验证、超参数优化、评价指标等内容 机器学习-面经(part3)-正则化、特征工程面试问题与解答合集机器学习-面经(part4)-决策树共5000字的面试问…

go linux监测文件变化

go linux监测文件变化 文件改变内容有两种方式&#xff0c;效果一样&#xff0c;但执行方式有区别: 直接打开文件改&#xff0c;现在很多编辑器都是这样操作的先删除原来的&#xff0c;再新创建写入一个替代原来的。比如vi/vim.这种方式会打断linux inotify原有的监测(就好比…

springboot+vue+mysql项目使用的常用注解

实体类常用注解 Data Data 是一个 Lombok 提供的注解&#xff0c;使用 Data 注解可以简化代码&#xff0c;使代码更加简洁易读。 作用&#xff1a;自动为类生成常用的方法&#xff0c;包括 getter、setter、equals、hashCode 和 toString 等需要加Lombok的依赖 <depende…

vue系列——vscode,node.js vue开发环境搭建

第一步安装node.js 推荐使用nvm进行node.js 的安装 nvm(Node.js version manager) 是一个命令行应用&#xff0c;可以协助您快速地 更新、安装、使用、卸载 本机的全局 node.js 版本。 可以去网上查找相关版本 我这里使用 nvm-setu… 链接:https://pan.baidu.com/s/1UEUtmzw5x…

【数据结构】红黑树(RBTree)

介绍 概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出两倍&#xff0c;因而是…