刷题笔记4 | 24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
输入:head = [1,2,3,4] 输出:[2,1,4,3]
此题说明了只能进行节点交换。其实按要求改变结点走向就行了
设置一个虚拟头结点cur
1、每次cur->next = cur->next->next; 就完成了步骤一
2、对于步骤二,其实只需要先把要指向的结点保存一下,然后再改指向。
ListNode* tmp = cur->nxet;
cur->next = cur->next->next; // 完成步骤一
cur->next->next = tmp; //完成步骤二
3、对于步骤三,同样可以先保存,再改指向
ListNode* tmp = cur->nxet;
ListNode* tmp1 = cur->nxet->next->next;
cur->next = cur->next->next; // 完成步骤一
cur->next->next = tmp; //完成步骤二
cur->nxet->next->next = tmp1; //完成步骤三
4、接下来循环便重复操作就行了
cur = cur->nxet->next;
对于循环条件有以下解释:
while (prev.next != nu11 && prev.next.next != nu11)
这边为什么是&& 不是|| 一个是对于偶数个结点的判断 一个是奇数个结点 那不应该是||的关系吗?
奇数节点就不需要交换了,所以只有满足后面有偶数个节点的时候才会进入循环- 循环条件,什么情况应该判断指针本身为空呢?
可以看这个这个遍历的指针最后需要走到哪里 需不需要对最后一个节点做操作
C++版本:
/*** 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) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* tmp = cur->next;ListNode* tmp1 = cur->next->next->next;cur->next = cur->next->next;cur->next->next = tmp;cur->next->next->next = tmp1;cur = cur->next->next;}head = dummyHead->next;delete dummyHead;return head;}
};
Python版本:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummyHead = ListNode()dummyHead.next = headcur = dummyHeadwhile(cur.next != None and cur.next.next != None):tmp = cur.nexttmp1 = cur.next.next.nextcur.next = cur.next.nextcur.next.next = tmpcur.next.next.next = tmp1cur = cur.next.nextreturn dummyHead.next
19. 删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
解法一:
拿到这个题,第一想法是计算出整个长度L,然后删除第L+1-n个结点。
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;int L = 0;while(cur->next!=nullptr){ //计算长度LL++;cur = cur->next;}ListNode* cur1 = dummyHead;for(int i = 0; i<L-n; i++){ //移动到删除结点的前一结点cur1 = cur1->next;}ListNode* tmp = cur1->next;cur1->next = cur1->next->next;delete tmp;head = dummyHead->next;delete dummyHead;return head;}
};
解法二:双指针法,不得不说卡哥的双指针法用得太多了
其思想是定义fast指针和slow指针,初始值为虚拟头结点,f
ast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作)fast和slow同时移动,直到fast指向末尾,此时slow指向需要删除的前一结点。再删除相应结点即可。
C++版本:
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* fast = dummyHead;ListNode* slow = dummyHead;while(n--){fast = fast->next;}fast = fast->next; //fast 走n+1步while(fast != nullptr){fast = fast->next;slow = slow->next; //slow移动到删除结点的前一结点}slow->next = slow->next->next; //删除slow后一结点head = dummyHead->next;delete dummyHead;return head; }
};
Python版本:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummyHead = ListNode()dummyHead.next = headfast = dummyHeadslow = dummyHeadn += 1while(n):n -= 1fast = fast.nextwhile(fast!=None):fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummyHead.next
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
思路:
简单来说,就是求两个链表交点节点的指针。 这里同学们要注意,交点不是数值相等,而是指针相等。
由于是求相交节点,那么对AB来说,从相交结点到末尾结点的长度是相等的。于是可以定义两个指针,假设A链表长度更长,CurA指向A的Head,CurB指向B的Head,求出A的长度LA,B的长度LB,先让A移动LA-LB的位置,此时CurA和CurB再一起移动,通过判断地址是否相等,就可以得出是否有相交结点。
C++版本:直接抄了,不难。
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB = 0;while (curA != NULL) { // 求链表A的长度lenA++;curA = curA->next;}while (curB != NULL) { // 求链表B的长度lenB++;curB = curB->next;}curA = headA;curB = headB;// 让curA为最长链表的头,lenA为其长度if (lenB > lenA) {swap (lenA, lenB);swap (curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上(末尾位置对齐)while (gap--) {curA = curA->next;}// 遍历curA 和 curB,遇到相同则直接返回while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}return NULL;}
};
142.环形链表II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。
输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。
解法思路:
1、判断是否有环:可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。
2、如果有环,如何找到这个环的入口
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。
slow指针走的数目: x+y
fast指针走的数目:x+y+n(y+z)
由于:fast指针走过的节点数 = slow指针走过的节点数 * 2
则 (x + y) * 2 = x + y + n (y + z)
则 x + y = n (y + z)
则 x = n (y + z) - y = (n - 1) (y + z) + z
当 n为1的时候,公式就化解为 x = z
,这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。
那么 n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。
C++版本:直接借鉴代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;// 快慢指针相遇,此时从head 和 相遇点,同时查找直至相遇if (slow == fast) {ListNode* index1 = fast;ListNode* index2 = head;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index2; // 返回环的入口}}return NULL;}
};
相关文章:

刷题笔记4 | 24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
24. 两两交换链表中的节点 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 输入:head [1,2,3,4] 输出:…...

15、正则表达式
目录 一、元字符 二、限定修饰符 一、元字符 正则表达式通常被用于判断语句中,用来检查某一字符串是否满足某一格式。正则表达式是含有一些具有特殊意义字符的字符串,这些特殊字符称为正则表达式的元字符。例如,“\\d”表示数字0~9中的任何…...

javaWeb核心01-HTTPTomcatServlet
文章目录HTTP&Tomcat&Servlet1,Web概述1.1 Web和JavaWeb的概念1.2 JavaWeb技术栈1.2.1 B/S架构1.2.2 静态资源1.2.3 动态资源1.2.4 数据库1.2.5 HTTP协议1.2.6 Web服务器1.3 Web核心课程安排2, HTTP2.1 简介2.2 请求数据格式2.2.1 格式介绍2.2.2 实例演示2.…...
深圳大学计软《面向对象的程序设计》实验16 期末复习
A. 一、会员积分(期末模拟) 题目描述 某电商网站的会员分为:普通、贵宾两个级别 普通会员类Member,包含编号、姓名、积分三个属性,编号和积分是整数,姓名是字符串 操作包括构造、打印、积分累加、积分兑…...
Linux基础命令(一)
文章目录1、时间命令:date2、日历命令:cal3、计算器程序:bc4、基础组合键5、正确的关机指令使用5.1 将数据同步写入硬盘中的指令: sync5.2 惯用的关机指令: shutdown5.3 重新开机,关机: reboot,…...

RocketMQ Broker消息处理流程剩余源码解析
🍊 Java学习:Java从入门到精通总结 🍊 深入浅出RocketMQ设计思想:深入浅出RocketMQ设计思想 🍊 绝对不一样的职场干货:大厂最佳实践经验指南 📆 最近更新:2023年3月4日 …...
JQuery入门基础
目录 1.初识 下载 使用 JQuery(核心)对象 2.选择器 基础选择器 层次选择器 后代选择器 子代选择器 兄弟选择器 相邻选择器 3.JQuery DOM操作 创建元素 插入元素 删除元素 遍历元素 属性操作 获取属性 设置属性 删除属性 样式操作 …...
kafka 构建双向SSL认证
kafka 安装 以下内容均已完成测试,按照教程搭建你会得到一个双向ssl认证的kafka broker,并能通过ip以及域名访问,笔者能力有限如果文章内容存在问题烦请各位指出。 搭建单机Kafka 需求 centos 7kafka_2.12-2.6.0jdk8(文档中统…...

推荐一个.Net Core开发的Websocket群聊、私聊的开源项目
更多开源项目请查看:一个专注推荐.Net开源项目的榜单 今天给大家推荐一个使用Websocket协议实现的、高性能即时聊天组件,可用于群聊、好友聊天、游戏直播等场景。 项目简介 这是一个基于.Net Core开发的、简单、高性能的通讯组件,支持点对点…...
华为OD机试Golang解题 - 事件推送 | 含思路
华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典文章目录 华为Od必看系列使用说明本期题目…...

将微信小程序页面转为图片
最近做项目遇到一个需求,那就是要将某个页面转为图片然后传给后端,我仔细找了一圈,发现官方那个Api也就是wx.canvasToTempFilePath生成的图片很有可能为空,太坑了,于是我放弃用它了,选择了用wxml2canvas。 安装wxml2canvas npm init npm install wxml2canvas --save --…...

LINE、SDNE和struc2vec图嵌入算法学习笔记
引言 在cs224w课程中,我先后总结了deepwalk、node2vec,这两种算是最经典也是最主流的做法,而在 图节点嵌入相关算法学习笔记 中,从头至尾,将一些经典算法用wiki的数据集复现了一下,所以本篇博文࿰…...

Buuctf Younger-drive 题解
目录 一.查壳 二.运行缺少dll 三.主函数 四.hObject线程 五.Thread线程 六.judge函数 七.解题脚本 这题的关键在于了解一定的线程相关知识 一.查壳 32位带壳,用upx脱壳 二.运行缺少dll 后续尝试了各种方法修复dll但是还是运行不了 值得一提的是脱壳后的程序不能动态调试…...
数据结构与算法:二叉树专题
数据结构与算法:二叉树专题前言前提条件基础知识二叉树链式存储结构二叉树中序遍历二叉树层序遍历常见编程题把一个有序整数数组放到二叉树中逐层打印二叉树结点数据求一棵二叉树的最大子树和判断两棵二叉树是否相等把二叉树转换为双向链表判断一个数组是否是二元查…...
Cadence Allegro 导出Cadence Schematic Feedback Report详解
⏪《上一篇》 🏡《总目录》 ⏩《下一篇》 目录 1,概述2,Cadence Schematic Feedback Report作用3,Cadence Schematic Feedback Report示例4,Cadence Schematic Feedback Report导出方法4.1,方法1,4.2,方法2,...
《计算机系统基础》—— 运算
文章目录《计算机系统基础》——运算整数按位运算作用操作位移运算作用操作乘法运算除法运算浮点数加减运算乘除运算《计算机系统基础》——运算 🚀🚀本章我们需要介绍的是有关C语言里面的运算,当然了,我们不会是介绍简单的运算&…...

MSTP多进程讲解与实验配置
目录 MSTP多进程 专业术语 MSTP多进程配置 在MSTP域配置 MSTP多进程 多进程的作用 将设备上的端口绑定到不同的进程中,以进程为单位进行MSTP计算,不在同一进程内的端口不参与此进程中的MSTP协议计算,实现各个进程之间的生成树计算相互独立…...
【Python】软件测试必备:了解 fixture 在自动化测试中的重要作用
在自动化软件测试中,fixture 是一种确保测试在一致且受控条件下运行的重要方法。简单来说,fixture 就是一组先决条件或固定状态,必须在运行一组测试之前建立。在测试框架中,fixture 提供了一种方便的方法,用于在每个测…...
DevExpress皮肤引用的办法
1.引用Dll皮肤文件Typeprocedure SetSkin(skinnam:string);procedure TFrmMain.SetSkin(skinnam:string);varHinst:THANDLE;RStream:TResourceStream;beginHinst:Loadlibrary(ALLSK.dll);If Hinst0 ThenExitelsebeginRstream:TResourceStream.Create(Hinst,skinnam,MYSKIN);dxS…...
2023-03-04 区分纳米颗粒核壳原子
声明:未经允许,不得擅自复制、转载。欢迎引用:Laser-Assisted Synthesis of Bi-Decorated Pt Aerogel for Efficient Methanol Oxidation ElectrocatalysisApplied Surface Science ( IF 6.707 ) Pub Date : 2022-04-01 , DOI: 10.1016/j.aps…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...