DS:顺序表、单链表的相关OJ题训练(2)

欢迎各位来到 Harper.Lee 的学习世界!

博主主页传送门:Harper.Lee的博客主页

想要一起进步的uu欢迎来后台找我哦!


一、力扣--141. 环形链表

        题目描述:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 。 否则,返回 false 。

        常见环形链表有以下几种:(环形链表不清楚最后一个节点即尾节点在哪里的)。

        常见的一种判断链表是否带环的错误方法:某节点的next指针和遍历的pcur的next指针相同,就认为该链表带环。这是错误的!!! 因为我们不知道遍历的pcur指针是否进环,他可能在环外,也可能在环内。

最好的办法就是使用快慢指针追击:慢指针slow一次走一步,快指针fast一次走两步。当

bool hasCycle(struct ListNode *head) {struct ListNode* slow = head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//两个nextif(slow == fast)return true;}return false;
}

Q1:为什么一定会相遇?

        假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。

Q2:快指针一次走3步,走4步,...n步行吗?

根据分析可知,快慢指针的追击问题不在于两者一次走多少步,而在于快慢指针之间的速度差

分析过程图片:

Q3:有没有可能会错过,永远追不上?

分析过程图片: 

       所以答案是:一定会追上,一定能追上!

二、力扣--142. 环形链表 II

 题目描述:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

三、力扣---02.02. 返回倒数第 k 个节点

思路一:创建一个新数组,在数组中寻找相应的数据,返回数据对应的下标。(空间复杂度高了)

思路二:第一遍遍历得出节点个数(n),如果要求找倒数第k个节点,就去找正数第n-k+1个节点,并返回该节点的值。

思路三(在思路二的基础上要求空间复杂度O(1),也就是只能遍历链表一遍):快慢指针法。fast先走k步,拉开差距,然后两个指针再同时移动。注意单链表是不能倒着走的。可以加一个判断:k小于等于链表长度。

int kthToLast(struct ListNode* head, int k){struct ListNode* fast = head,*slow = head;//均是从头节点开始///快指针先走k步(或者k-1步)while(k--){fast = fast->next;}while(fast)//快慢指针同时走,快指针先走到头{slow = slow->next;fast = fast->next;}return slow->val;
}

四、牛客--OR36 链表的回文结构

        题目描述:对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。如:1->2->2->1,返回true。

单链表有奇数个和偶数个两种情况:1、先查找中间节点;2、后半段逆置。

代码如下:

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//查找中间节点 
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow =head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){struct ListNode* next =cur->next;//头插cur->next=newhead;newhead = cur;cur = next;}return newhead;
}bool chkPalindrome(ListNode* A) {struct ListNode* mid = middleNode(A);//查找中间节点struct ListNode* rmid = reverseList(mid);//逆置后半段while(rmid && A)//有一个为空,就结束了,则都不为空进入循环{if(rmid->val!=A->val)return false;rmid = rmid->next;}return true;}
};

五、力扣--160. 相交链表

        题目描述:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。图示两个链表在节点 c1 开始相交

 

         链表的相交的形式:不是X字型,而是Y字型, 因为单链表的一个节点只能有一个next指针。

         思路一:A链表逐个结点与B链表比较,如果存在相等,则就是相交结点(注:要比较指针而不能比较值,因为值是可以重复的)。
        具体过程分析:1. 判断两个链表是否相交:判断两个链表的尾指针是否相等,相等则两个链表相交,注意用地址来判断而不是值。2. 若相交,找出第一个交点:用暴力求解,链表A的节点依次和链表B的所有节点比较一遍(比较地址,而不是值),如果链表A的某个节点和链表B相等,则这个节点就是交点。 最坏情况:不相交,时间复杂度:O(m*n)(两个链表的长度)。

        思路二:长的链表往前走长度差到短链表开头,再同时走,直到相等就是相交点。    

        最坏的情况:最后一个才遇到交点。F(n)=3*N,时间复杂度O(N)。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA,*curB= headB;int lenA = 1,lenB = 1;//计算链表长度while(curA->next){curA = curA->next;++lenA;}while(curB->next){curB = curB->next;++lenB;}//尾节点不相等就是相交if(curA != curB){return NULL;}//长链表先走差距步,两个链表再同时走,第一个相等就是交点//假设法:让逻辑更加简单int gap = abs(lenA - lenB);struct ListNode* longList = headA,*shortList = headB;if(lenB > lenA){longList =headB;shortList= headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return shortList;
}


创作不易,喜欢的uu三连支持一下叭! 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

burp靶场xss漏洞(初级篇)

靶场地址 http://portswigger.net/web-security/all-labs#cross-site-scripting 第一关&#xff1a;反射型 1.发现搜索框直接注入payload <script>alert(111)</script> ​ 2.出现弹窗即说明攻击成功 ​ 第二关&#xff1a;存储型 1.需要在评论里插入payload …

TriCore: Architecture

说明 本文是 英飞凌 架构文档 TriCore TC162P core archiecture Volume 1 of 2 (infineon.com) 的笔记&#xff0c;稍作整理方便查阅&#xff0c;错误之处&#xff0c;还请指正&#xff0c;谢谢 :) 1. Architecture 2. General Purpose & System Register 名词列表&#…

【全部更新】2024数维杯B题详细成品文章代码思路结果分享

生物质和煤共热解问题的研究 摘要 这个问题背景主要涉及生物质和煤共热解的研究。在共热解过程中&#xff0c;生物质和煤一起在高温和缺氧条件下热解&#xff0c;产生气体、液体和固体产物。研究生物质和煤共热解油的产率和品质机理对提高能源利用效率、促进资源综合利用和确保…

【YOLO 系列】基于YOLO V8的金属表面缺陷检测检测识别系统【python源码+Pyqt5界面+数据集+训练代码】

前言&#xff1a; 金属表面缺陷的及时检测对于保障产品质量和生产安全至关重要。然而&#xff0c;传统的人工检测方法往往效率低下、耗时长&#xff0c;并且容易受主观因素影响。为了解决这一问题&#xff0c;我们提出了基于深度学习技术的金属表面缺陷检测系统。 本项目采用…

Windows下安装Node.js、npm和electronic,并运行一个Hello, World!脚本程序

20240510 By wdhuag 目录 简介&#xff1a; 参考&#xff1a; 安装Node.js 安装npm 配置npm&#xff1a; 修改包存放目录和缓存目录 切换镜像源 使用 nrm 切换镜像源 安装Electron 运行一个Hello, World!脚本程序 安装Yarn JavaScript 指南 简介&#xff1a; Nod…

pdffactory pro8.0虚拟打印机(附注册码)

PdfFactory pro是一款非常受欢迎的PDF虚拟打印机&#xff0c;可以帮助用户将你的其他文档保存为PDF格式。请为用户提供打印/发送/加密等多种实用功能&#xff0c;以及一套完善的PDF打印方案。 使用说明 下载pdfFactory Pro压缩包&#xff0c;解压后&#xff0c;双击exe文件&am…

好景盒式磁带随声听

少年时代柜子里翻出来的磁带录音机电路板 两颗芯片&#xff0c;FM芯片&#xff0c;电机驱动 CD9088CBD6650

力扣HOT100 - 739. 每日温度

解题思路&#xff1a; 单调栈 class Solution {public int[] dailyTemperatures(int[] temperatures) {int length temperatures.length;int[] ans new int[length];Deque<Integer> stack new LinkedList<>();for (int i 0; i < length; i) {int temperatu…

BW4HANA混合建模 用ADSO的哪个视图?

写日志的ADSO除了1,2,3表之外。还会有6,7,8view。8view是上了BW4HANA2.0之后激活ADSO就会生成的。如果旧版本没有8&#xff0c;那就RSDG_ADSO_ACTIVATE激活一下。 如果勾了外部HANA视图&#xff0c;那就等于说还有一个HANA view。 首先咱知道ADSO是BW里面用来物理存储&#xf…

十大排序算法之->希尔排序

一、希尔排序简介 希尔排序&#xff0c;也称为缩小增量排序&#xff0c;是由D.L. Shell于1959年提出的。它的核心思想是将整个待排序的记录序列分割成若干个子序列&#xff0c;这些子序列的元素是相隔一定“增量”的。然后对这些子序列分别进行直接插入排序。随着增量的逐步减…

基于flowable没有规则的并发网关流程跳转记录分析

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

从传统到现代:水表的远程抄表革命

1.引言&#xff1a;技术驱动的转型 在过去的几十年里&#xff0c;我们的生活方式被科技的快速发展深深影响&#xff0c;其中就包括了公用设施的管理方式。传统水表的远程抄表系统就是这样一个例子&#xff0c;它将老旧的手动抄表模式转变为高效、精确的自动化系统。 2.传统水…

JUC下的CompletableFuture详解

详细介绍 CompletableFuture是Java 8引入的一个实现Future接口的类&#xff0c;它代表一个异步计算的结果。与传统的Future相比&#xff0c;CompletableFuture提供了更丰富的功能&#xff0c;比如链式调用、组合异步操作、转换结果、异常处理等&#xff0c;极大地增强了Java在…

C语言:__attribute__((packed))

一、简介 在使用结构体的时候&#xff0c;经常要根据结构体的长度来进行相关判断。但是按照C语言的规则&#xff0c;会对不同类型的数据类型进行自动对齐。有时候就会造成一些问题&#xff0c;如果不需要使用自动对齐的功能&#xff0c;就需要使用到本章的关键字。 二、自动对…

ICode国际青少年编程竞赛- Python-4级训练场-while语句入门

ICode国际青少年编程竞赛- Python-4级训练场-while语句入门 1、 while Flyer.disappear():wait() Dev.step(2)2、 Dev.step(1) while Flyer.disappear():wait() Dev.step(5)3、 while Flyer[0].disappear():wait() Dev.step(3) Dev.step(-1) while Flyer[0].disappear():…

爬虫-无限debug场景 解决方式

解决无限debug 场景1 1. 鼠标右键 选择 continue to here&#xff08;此处不停留&#xff09;2. 鼠标右键 选择 edite breakpoint 设置 10 保证条件不成立 这行永远不执行3.方法置空 1. 方法调用加断点2. 控制台 setInterval function name() {}4. 替换文件 5. hoo…

【CSDN搜材料的小技巧】怎么快速查到高质量最新的内容

问题描述: 我最近搜CSDN已经搜累了&#xff0c;好多东西明显是有问题的&#xff0c;还有一堆人复制粘贴&#xff0c;从海量文章中提取出最新且高质量文章成了当务之急&#xff01; 解决方案: 我本来想写个爬虫按照文章的收藏或者点赞排序的&#xff0c;无意中看到了这篇文章…

msix packaging tool打包问题

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

FreeRTOS学习 -- 任务相关API函数

一、任务创建和删除API函数 FreeRTOS 最基本的功能就是任务管理&#xff0c;而任务管理最基本的操作就是创建和删除任务。 FreeRTOS的任务创建和删除API函数如下&#xff1a; 1、函数 xTaskCreate() 此函数用来创建一个任务&#xff0c;任务需要 RAM 来保存于任务有关的状…

子查询之二(不相关子查询与相关子查询)

1. 相关子查询 如果子查询的执行依赖于外部查询&#xff0c;通常情况下都是因为子查询中的表用到了外部的表&#xff0c;并进行的条件关联&#xff0c;因此每一次执行一次外部查询&#xff0c;子查询都会重新计算一次&#xff0c;这样的子查询称为关联子查询. 相关子查询按照…