LeetCode 热题 100 | 链表(中下)

目录

1  19. 删除链表的倒数第 N 个节点

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

3  25. K 个一组翻转链表

4  138. 随机链表的复制


菜鸟做题第三周,语言是 C++

1  19. 删除链表的倒数第 N 个节点

到底是节点还是结点。。。

解题思路:

  1. 设置双指针 left 和 right
  2. 先让 right 右移 n 格
  3. 再让 left 和 right 一起右移直至 right 指向 nullptr
  4. left 将恰好处于被删除节点的前一个节点

思路说明图:

这个虚拟节点(dummy node)的设置非常巧妙,完美处理了被删除节点是头节点的情况。

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode * dummy = new ListNode(0, head);ListNode * left = dummy, * right = head;for (int i = 0; i < n; ++i) {right = right->next;}while (right) {left = left->next;right = right->next;}left->next = left->next->next;return dummy->next;}
};

虽然不设置虚拟节点(dummy node)也能做,但是写 if 语句的模样真的很狼狈。

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

思路很简单,一组一组地交换即可,关键在于保存需要再次使用到的节点指针。

public:ListNode* swapPairs(ListNode* head) {ListNode * dummy = new ListNode(0, head);ListNode * prev = dummy, * post = nullptr;ListNode * left = head, * right = head ? head->next : nullptr;while (left && right) {post = right->next;right->next = left;left->next = post;prev->next = right;prev = left;left = post ? post : nullptr;right = post ? post->next : nullptr;}return dummy->next;}
};

说明:以下是为了防止指针越界而进行的判断

left = post ? post : nullptr;
right = post ? post->next : nullptr;

3  25. K 个一组翻转链表

是上一题的升级版。

解题思路:

  • 设置 prev、left、right、temp、next 指针
  • prev 用于保存上一组的尾巴
  • left 用于保存当前组的头部
  • right 和 temp 一起右移,对每一个指针进行反向

是不是看起来很烦,但确实可能要使用到很多指针。

我加了一个函数来判断剩余部分还能不能构成 K 个一组:

bool isEnough(ListNode * p, int k) {int count = 0;while (p && count < k) {p = p->next;++count;}return count == k;
}

 其实思路也不难,就是容易转晕:

class Solution {
public:bool isEnough(ListNode * p, int k) {int count = 0;while (p && count < k) {p = p->next;++count;}return count == k;}ListNode* reverseKGroup(ListNode* head, int k) {ListNode * dummy = new ListNode(0, head);ListNode * left = head, * right = head->next;ListNode * prev = dummy;while (isEnough(left, k)) {int count = 1;ListNode * temp = left;while (count < k) {++count;ListNode * next = right->next;right->next = temp;temp = right;right = next;}prev->next = temp;prev = left;left->next = right;left = right;right = left ? left->next : nullptr;}return dummy->next;}
};

4  138. 随机链表的复制

这道题用递归真是太神奇了,可惜我不会。。。

class Solution {
public:unordered_map<Node *, Node *> cachedNode;Node* copyRandomList(Node* head) {if (head == nullptr) return nullptr;if (!cachedNode.count(head)) {Node * headNew = new Node(head->val);cachedNode[head] = headNew;headNew->next = copyRandomList(head->next);headNew->random = copyRandomList(head->random);}return cachedNode[head];}
};

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

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

相关文章

聊聊比特币----比特币地址

⽐特币地址是⼀个标识符&#xff08;帐号&#xff09;&#xff0c;地址可以以QR码形式表⽰&#xff0c;是匿名的&#xff0c;不包含关于所有者的信息。 ⼤多数⽐特币地址(P2PKH,P2SH)是34个字符。它们由随机数字和⼤写字母及⼩写字母组成&#xff0c;除了⼤写字母“O”&#x…

前端复杂 table 渲染及 excel.js 导出

转载请注明出处&#xff0c;点击此处 查看更多精彩内容 现在我们有一个如图&#xff08;甚至更复杂&#xff09;的表格需要展示到页面上&#xff0c;并提供下载为 excel 文件的功能。 前端表格渲染我们一般会使用 element-ui 等组件库提供的 table 组件&#xff0c;这些组件一般…

css3 属性 backface-visibility 的实践应用

backface-visibility 是一个用于控制元素在面对屏幕不同方向时的可见性的CSS3特性。它有两个可能的值&#xff1a; visible&#xff1a;当元素不面向屏幕&#xff08;即背面朝向用户&#xff09;时&#xff0c;元素的内容是可以被看到的。hidden&#xff1a;当元素不面向屏幕…

day32 买卖股票的最佳时机Ⅱ 跳跃游戏 跳跃游戏Ⅱ

题目1&#xff1a;122 买卖股票的最佳时机Ⅱ 题目链接&#xff1a;122 买卖股票的最大时机Ⅱ 题意 整数数组prices[i]表示某股票的第i天的价格&#xff0c;每天可买卖股票且最多持有1股股票&#xff0c;返回最大利润 利润拆分&#xff0c;拆分为每天的利润 每天的正利…

基于若依的ruoyi-nbcio流程管理系统自定义业务回写状态的一种新方法(二)

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/n…

【八大排序】选择排序 | 堆排序 + 图文详解!!

&#x1f4f7; 江池俊&#xff1a; 个人主页 &#x1f525;个人专栏&#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 &#x1f305; 有航道的人&#xff0c;再渺小也不会迷途。 文章目录 一、选择排序1.1 基本思想1.2 算法步骤 动图演示1.3 代码实现1.4 选择排序特性总结 二…

Vue3项目封装一个Element-plus Pagination分页

前言:后台系统分页肯定是离不开的,但是ui框架都很多,我们可以定义封装一种格式,所有项目按到这个结构来做. 实例: 第一步:在项目components组件新建一个分页组件,用来进行封装组件. 第二步:根据官方的进行定义,官方提供的这些,需要我们封装成动态模式 第三步:代码改造 <!-…

aspose-words基础功能演示

我们在Aspose.Words中使用术语“渲染”来描述将文档转换为文件格式或分页或具有页面概念的介质的过程。我们正在讨论将文档呈现为页面。下图显示了 Aspose.Words 中的渲染情况。 Aspose.Words 的渲染功能使您能够执行以下操作: 将文档或选定页面转换为 PDF、XPS、HTML、XAML、…

MySQL操作问题汇总

MySQL操作问题汇总 1.无法远程连接Ubuntu的MySQL2.ubuntu忘记mysql的root密码时的操作 1.无法远程连接Ubuntu的MySQL (1) 需要检查防火墙状态 > sudo ufw status #如果防火墙开启的情况&#xff0c;添加规则&#xff1a;允许3306端口开启 > sudo ufw allow 3306 (2) 需要…

计算机网络_1.6.3 计算机网络体系结构分层思想举例

1.6.3 计算机网络体系结构分层思想举例 1、实例引入&#xff08;用户在主机中使用浏览器访问web服务器&#xff09;2、从五层原理体系结构的角度研究该实例3、练习题 笔记来源&#xff1a; B站 《深入浅出计算机网络》课程 本节通过一个常见的网络应用实例&#xff0c;来介绍计…

【论文阅读笔记】Advances in 3D Generation: A Survey

Advances in 3D Generation: A Survey 挖个坑&#xff0c;近期填完摘要 time&#xff1a;2024年1月31日 paper&#xff1a;arxiv 机构&#xff1a;腾讯 挖个坑&#xff0c;近期填完 摘要 生成 3D 模型位于计算机图形学的核心&#xff0c;一直是几十年研究的重点。随着高级神经…

计算机设计大赛 深度学习+opencv+python实现昆虫识别 -图像识别 昆虫识别

文章目录 0 前言1 课题背景2 具体实现3 数据收集和处理3 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数&#xff1a;2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 4 MobileNetV2网络5 损失函数softmax 交叉熵5.1 softmax函数5.2 交叉熵损失函数 6 优化器SGD7 学…

H5 加密(MD5 Base64 sha1)

1. 说明 很多的时候是避免不了注册登录这一关的&#xff0c;但是一般的注册是没有任何的难度的&#xff0c;无非就是一些简单的获取用户输入的数据&#xff0c;然后进行简单的校验以后调用接口&#xff0c;将数据发送到后端&#xff0c;完成一个简单的注册的流程&#xff0c;那…

python的进程,线程、协程

python进程的实现 #coding:utf-8 from multiprocessing import Process import timedef run(name):print(%s is running % name)time.sleep(3)print(%s finished his run % name)if __name__ __main__:p Process(targetrun, args(XWenXiang,)) # 创建一个进程对象p.start()…

Jvm FullGC 如何排查?

使用场景 我们在使用系统时&#xff0c;有时请求和响应会变得特别慢&#xff0c;系统也变得很卡。 有可能是FullGC的问题&#xff0c;可以逐步地进行排查。 使用jps和top确定进程号pid jps可以列出正在运行的jvm进程&#xff0c;并显示jvm执行主类名称( main()函数所在的类…

Android Button background 失效

问题 Android Button background 失效 详细问题 笔者开发Android项目&#xff0c;期望按照 android:background中所要求的颜色展示。 实际显示按照Android 默认颜色展示 解决方案 将xml的Button 组件修改为<android.widget.Button> 即将代码 <Buttonandroid:l…

oracle数据库慢查询SQL

目录 场景&#xff1a; 环境&#xff1a; 慢SQL查询一&#xff1a; 问题一&#xff1a;办件列表查询慢 分析&#xff1a; 解决方法&#xff1a; 问题二&#xff1a;系统性卡顿 分析&#xff1a; 解决方法&#xff1a; 慢SQL查询二 扩展&#xff1a; 场景&#xff1a; 线…

用Audio2Face导出Unity面部动画

开始之前说句话&#xff0c;新年前最后一篇文章了 一定别轻易保存任何内容&#xff0c;尤其是程序员不要轻易Ctrl S 在A2F去往Unity的路上&#xff0c;还要经历特殊Blender&#xff0c;自己电脑中已下载好的可能不是很好使。 如果想查看UE相关的可以跳转到下边这两篇链接 1. …

【51单片机】LED的三个基本项目(LED点亮&LED闪烁&LED流水灯)(3)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

瑞_23种设计模式_工厂模式

文章目录 1 什么是工厂模式案例案例代码 2 简单工厂模式&#xff08;Simple Factory&#xff09;2.1 简单工厂模式的结构2.2 案例改进——简单工厂模式2.3 案例改进代码实现2.4 简单工厂模式优缺点2.5 拓展——静态工厂 3 工厂方法模式&#xff08;Factory Method&#xff09;★…