当前位置: 首页 > news >正文

LeetCode 热题100(七)【链表】(2)

目录

7.6合并两个有序链表(简单)

7.7两数相加(中等)

7.8删除链表的倒数第N个节点(中等)

7.9两两交换链表中的节点(中等)

7.10k个一组翻转链表(困难)


7.6合并两个有序链表(简单)

题目描述:leetcode链接 21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

思路:

1.当list1为空链表,直接返回list2;当list2为空链表,直接返回list1

2.当list1、list2均为非空链表,比较list1 -> val和list2 -> val的大小

如果list1 -> val > list2 -> val,则list2 -> next = mergeTwoLists(list1, list2 -> next);

否则list1 -> next = mergeTwoLists(list1 -> next, list2)

举例说明:

代码:

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) return list2;else if (!list2) return list1;else if (list1 -> val > list2 -> val) {list2 -> next = mergeTwoLists(list1, list2 -> next);return list2;}else {list1 -> next = mergeTwoLists(list1 -> next, list2);return list1;}}
};

7.7两数相加(中等)

题目描述:leetcode链接 2.两数相加

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

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

你可以假设除了数字 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]

思路:

1.add用于存储进位,新建哑结点ListNode* dummy = new ListNode(0)用于存储相加后的结果

ListNode* cur = dummy

2.只要l1 || l2 || add满足条件

int n1 = l1 ? l1 -> val : 0;(如果l1不是nullptr,n1=l1 -> val,否则n1=0)
int n2 = l2 ? l2 -> val : 0;(如果l2不是nullptr,n2=l2 -> val,否则n2=0)
int sum = n1 + n2 + add;

sum%10:存储结果

add = sum/10:更新进位结果

3.移动至链表的下一节点,重复第2步

cur = cur -> next;
if (l1) l1 = l1 -> next;
if (l2) l2 = l2 -> next;

4.最后返回dummy -> next

举例说明:

见上图

代码:

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int add = 0;ListNode* dummy = new ListNode(0);ListNode* cur = dummy;while (l1 || l2 || add) {int n1 = l1 ? l1 -> val : 0;int n2 = l2 ? l2 -> val : 0;int sum = n1 + n2 + add;cur -> next = new ListNode(sum % 10);cur = cur -> next;add = sum / 10;if (l1) l1 = l1 -> next;if (l2) l2 = l2 -> next;}ListNode* ans = dummy -> next;delete dummy;return ans;}
};

7.8删除链表的倒数第N个节点(中等)

题目描述:leetcode链接 19. 删除链表的倒数第N个节点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

思路:

1.新建哑结点ListNode* dummy指向链表的头节点

2.利用快慢指针fast和slow,均从dummy开始,首先令fast向前走N步

3. fast和slow同步向前移动,当fast到达链表末端时,slow到达待删除节点的上一个节点

4.令slow -> next = slow -> next -> next,返回dummy -> next

举例说明:

见上图

代码:

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0);dummy -> next = head;ListNode* fast = dummy;ListNode* slow = dummy;while (n--) {if (fast -> next) fast = fast -> next;else return nullptr;}while (fast -> next) {fast = fast -> next;slow = slow -> next;}slow -> next = slow -> next -> next;return dummy -> next;}
};

7.9两两交换链表中的节点(中等)

题目描述:leetcode链接 24. 两两交换链表中的节点

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

示例 1:

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

示例 2:

输入:head = []
输出:[]

示例 3:

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

思路:

举例说明:

见上图

代码:

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummy = new ListNode(0);dummy -> next = head;ListNode* cur = dummy;while (cur -> next && cur -> next -> next) {ListNode* node1 = cur -> next;ListNode* node2 = cur -> next -> next;cur -> next = node2;node1 -> next = node2 -> next;node2 -> next = node1;cur = node1;}return dummy -> next;}
};

7.10k个一组翻转链表(困难)

题目描述:leetcode链接 25. k个一组翻转链表

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

思路:

1.遍历链表,统计节点个数为n

2.每k个节点翻转一次链表

3.对已翻转的k个节点与前后节点之间的关系进行更新

举例说明:

每k个节点翻转一次:参考7.2反转链表

已翻转的k个节点与前后节点的关系更新:参考7.9两两交换链表中的节点

代码:

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int n = 0;ListNode* dummy = new ListNode(0);dummy -> next = head;ListNode* count = head;while (count) {n++;count = count -> next;} ListNode* pre = nullptr;ListNode* cur = head;ListNode* p0 = dummy;for (; n >= k; n -= k) {for (int i = 0; i < k; i++) {ListNode* temp = cur -> next;cur -> next = pre;pre = cur;cur = temp;}ListNode* temp2 = p0 -> next;p0 -> next -> next = cur;p0 -> next = pre;p0 = temp2;}return dummy -> next;}
};

http://www.lryc.cn/news/479350.html

相关文章:

  • 计算机网络 TCP/IP体系 网络层
  • 迈入国际舞台,AORO M8防爆手机获国际IECEx、欧盟ATEX防爆认证
  • 实习作假:阿里健康实习做了RABC中台,还优化了短信发送流程
  • Unity中IK动画与布偶死亡动画切换的实现
  • java导出word文件(手绘)
  • ssm070基于SSM框架的校园代购服务订单管理系统的设计与实现+vue(论文+源码)_kaic
  • Java项目实战II基于Spring Boot的秒杀系统设计与实现(开发文档+数据库+源码)
  • FastAPI —— 请求参数验证
  • 第七篇: BigQuery中的复杂SQL查询
  • 【SQL实验】高级查询(难点.三)含附加数据库操作
  • qt QFileSystemModel详解
  • element plus中修改el-table的样式
  • 深入理解封装与接口:Java程序设计的核心思想与最佳实践
  • linux 下调试 mpu6050 三轴加速度
  • C语言心型代码解析
  • 【LeetCode】【算法】647. 回文子串
  • 介绍6种常见的基于知识图谱推荐算法的类型和各自的优缺点
  • 使用python拟合二元曲线系数
  • go 集成viper 配置管理
  • Java:数据结构-再谈String类
  • 斗破QT编程入门系列之二:GUI应用程序设计基础:UI文件(四星斗师)
  • 微服务实战系列之玩转Docker(十八)
  • Javascript 获取设备信息 工具
  • 基于开源 AI 智能名片、S2B2C 商城小程序的用户获取成本优化分析
  • 仿真APP助力汽车零部件厂商打造核心竞争力
  • vue实现websocket实时短消息通知
  • tinymce扩展功能:1、行高、段落间距、格式刷;2、视频上传进度条;3、对复制的图片设置尺寸
  • 计算机毕业设计Python+图神经网络手机推荐系统 手机价格预测 手机可视化 手机数据分析 手机爬虫 Django Flask Spark 知识图谱
  • WPF的<ContentControl>控件
  • Python并发编程——multiprocessing