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

刷题笔记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. 两两交换链表中的节点 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 输入&#xff1a;head [1,2,3,4] 输出&#xff1a…...

15、正则表达式

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

javaWeb核心01-HTTPTomcatServlet

文章目录HTTP&Tomcat&Servlet1&#xff0c;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. 一、会员积分&#xff08;期末模拟&#xff09; 题目描述 某电商网站的会员分为&#xff1a;普通、贵宾两个级别 普通会员类Member&#xff0c;包含编号、姓名、积分三个属性&#xff0c;编号和积分是整数&#xff0c;姓名是字符串 操作包括构造、打印、积分累加、积分兑…...

Linux基础命令(一)

文章目录1、时间命令&#xff1a;date2、日历命令&#xff1a;cal3、计算器程序&#xff1a;bc4、基础组合键5、正确的关机指令使用5.1 将数据同步写入硬盘中的指令&#xff1a; sync5.2 惯用的关机指令&#xff1a; shutdown5.3 重新开机&#xff0c;关机&#xff1a; reboot,…...

RocketMQ Broker消息处理流程剩余源码解析

&#x1f34a; Java学习&#xff1a;Java从入门到精通总结 &#x1f34a; 深入浅出RocketMQ设计思想&#xff1a;深入浅出RocketMQ设计思想 &#x1f34a; 绝对不一样的职场干货&#xff1a;大厂最佳实践经验指南 &#x1f4c6; 最近更新&#xff1a;2023年3月4日 &#x1…...

JQuery入门基础

目录 1.初识 下载 使用 JQuery&#xff08;核心&#xff09;对象 2.选择器 基础选择器 层次选择器 后代选择器 子代选择器 兄弟选择器 相邻选择器 3.JQuery DOM操作 创建元素 插入元素 删除元素 遍历元素 属性操作 获取属性 设置属性 删除属性 样式操作 …...

kafka 构建双向SSL认证

kafka 安装 以下内容均已完成测试&#xff0c;按照教程搭建你会得到一个双向ssl认证的kafka broker&#xff0c;并能通过ip以及域名访问&#xff0c;笔者能力有限如果文章内容存在问题烦请各位指出。 搭建单机Kafka 需求 centos 7kafka_2.12-2.6.0jdk8&#xff08;文档中统…...

推荐一个.Net Core开发的Websocket群聊、私聊的开源项目

更多开源项目请查看&#xff1a;一个专注推荐.Net开源项目的榜单 今天给大家推荐一个使用Websocket协议实现的、高性能即时聊天组件&#xff0c;可用于群聊、好友聊天、游戏直播等场景。 项目简介 这是一个基于.Net Core开发的、简单、高性能的通讯组件&#xff0c;支持点对点…...

华为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课程中&#xff0c;我先后总结了deepwalk、node2vec&#xff0c;这两种算是最经典也是最主流的做法&#xff0c;而在 图节点嵌入相关算法学习笔记 中&#xff0c;从头至尾&#xff0c;将一些经典算法用wiki的数据集复现了一下&#xff0c;所以本篇博文&#xff0…...

Buuctf Younger-drive 题解

目录 一.查壳 二.运行缺少dll 三.主函数 四.hObject线程 五.Thread线程 六.judge函数 七.解题脚本 这题的关键在于了解一定的线程相关知识 一.查壳 32位带壳,用upx脱壳 二.运行缺少dll 后续尝试了各种方法修复dll但是还是运行不了 值得一提的是脱壳后的程序不能动态调试…...

数据结构与算法:二叉树专题

数据结构与算法&#xff1a;二叉树专题前言前提条件基础知识二叉树链式存储结构二叉树中序遍历二叉树层序遍历常见编程题把一个有序整数数组放到二叉树中逐层打印二叉树结点数据求一棵二叉树的最大子树和判断两棵二叉树是否相等把二叉树转换为双向链表判断一个数组是否是二元查…...

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,...

《计算机系统基础》—— 运算

文章目录《计算机系统基础》——运算整数按位运算作用操作位移运算作用操作乘法运算除法运算浮点数加减运算乘除运算《计算机系统基础》——运算 &#x1f680;&#x1f680;本章我们需要介绍的是有关C语言里面的运算&#xff0c;当然了&#xff0c;我们不会是介绍简单的运算&…...

MSTP多进程讲解与实验配置

目录 MSTP多进程 专业术语 MSTP多进程配置 在MSTP域配置 MSTP多进程 多进程的作用 将设备上的端口绑定到不同的进程中&#xff0c;以进程为单位进行MSTP计算&#xff0c;不在同一进程内的端口不参与此进程中的MSTP协议计算&#xff0c;实现各个进程之间的生成树计算相互独立…...

【Python】软件测试必备:了解 fixture 在自动化测试中的重要作用

在自动化软件测试中&#xff0c;fixture 是一种确保测试在一致且受控条件下运行的重要方法。简单来说&#xff0c;fixture 就是一组先决条件或固定状态&#xff0c;必须在运行一组测试之前建立。在测试框架中&#xff0c;fixture 提供了一种方便的方法&#xff0c;用于在每个测…...

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 区分纳米颗粒核壳原子

声明&#xff1a;未经允许&#xff0c;不得擅自复制、转载。欢迎引用&#xff1a;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…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...