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

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

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

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


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

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

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

       常见的判断链表是否带环的错误方法方法1. 判断遍历的指针的next指针是否为进环时的第一个节点指针。错误原因是:首先我们不清楚用来遍历的指针是否进环,此外,环外的部分很长也可能比较短,什么时候进环不能确定。方法2. 判断尾节点的next指针是否为空。错误原因:如果链表是带环的,我们并不能知道谁是最后一个节点,也可以说是带环链表没有尾节点。

最好的办法就是使用快慢指针追击:慢指针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 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//两个next(两步)//相遇:if(slow == fast){struct ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}

三、力扣---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://www.rhkb.cn/news/326537.html

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

相关文章

HTML学习|网页基本信息、网页基本标签、图像标签、超链接标签、列表标签、表格标签、媒体元素、页面结构分析、iframe内联框架

网页基本信息 DOCTYPE是设置使用什么规范,网页整个信息都在html标签中,head标签里包含字符集设置,网页介绍等信息,title标签是网页的名称,网页的主干都在body标签中 网页基本标签 标题标签 h1~h6都是标题标签&#x…

2024数维杯数学建模A题B题C题思路+模型+代码(开赛后第一时间更新)

2024数维杯数学建模A题B题C题思路模型代码(开赛后第一时间更新) https://mbd.pub/o/bread/ZpWakpdq https://mbd.pub/o/bread/ZpWakpdq 2024年第九届数维杯大学生数学建模挑战赛参赛规则 竞赛要求及论文提交方式; ①本次参赛作品统一在线提交到竞赛…

软件需求工程复习——知识点

一,单选题(20分) 二,判断题(10分) 三,简答题(20分) 四,分析与设计题(50分) 一、导论 1、应用型软件的模拟特性 应用型软件在“模拟”…

基于无监督学习算法的滑坡易发性评价的实施(k聚类、谱聚类、Hier聚类)

基于无监督学习算法的滑坡易发性评价的实施 1. k均值聚类2. 谱聚类3. Hier聚类4. 基于上述聚类方法的易发性实施本研究中的数据集和代码可从以下链接下载: 数据集实施代码1. k均值聚类 K-Means 聚类是一种矢量量化方法,最初来自信号处理,旨在将 N 个观测值划分为 K 个聚类,…

Web 安全漏洞之文件上传

目录 文件上传漏洞及危害 文件名 HTML 和 SVG 软链 服务器磁盘 防御方法 网络安全学习路线 (2024最新整理) 学习资料的推荐 1.视频教程 2.SRC技术文档&PDF书籍 3.大厂面试题 特别声明: 文件上传漏洞及危害 文件上传漏洞…

基于百川大语言模型的RSS新闻过滤应用【云服务器+公网网页,随时随地看自己DIY订阅的新闻内容】

背景 目前从公众号、新闻媒体上获得的新闻信息,都是经过算法过滤推荐的,很多时候会感到内容的重复性和低质量,因为他们也要考虑到自己的利益,并非完全考虑用户想要的、对用户有价值的信息。这时,如果要获取自己认为重要的信息,定制化开发自己的筛选算法更好。 效果 素材…

计算机网络(第八版 谢希仁 编著) 期末复习大纲

一.每章总结 第一章:分组交换,计网定义、范围划分,性能指标,五层体系结构,TCP/IP体系结构 第二章:物理层,码元,基带调制(数字信号->数字信号,也叫编码),带…

本来还挺喜欢……

前阵子买了个天空星开发板,到手之后发觉不对劲。 之前我们玩玩开发板都是用的面包板的,就算是ESP那种比较宽的板子用两个面包板拼一下也勉强可以用。 但是天空星它的引脚是分为两组,每组有两排,如果我们还是直接使用面包板的话&a…

浅析安全用电监控系统在工厂的研究与应用论述

摘 要:随着社会时代的发展,人们的安全意识越来越强烈,在人们生活和工作中离不开各种用电设备,用电设备的安全使用是保障人们生命安全的重要内容。工厂因自身厂内工作环境的特殊性,用电设备的种类多且复杂,如…

Meilisearch vs Elasticsearch

2个搜索引擎的比较(官方说法):Meilisearch vs Elasticsearch Elasticsearch 做为老牌搜索引擎,功能基本满足,但复杂,重量级,适合大数据量。 MeiliSearch 设计目标针对数据在 500GB 左右的搜索需…

【知识碎片】2024_05_13

本文记录了两道代码题【自除数】和【除自身以外数组的乘积】(利用了前缀积和后缀积,值得再看),第二部分记录了关于指针数组和逗号表达式的两道选择题。 每日代码 自除数 . - 力扣(LeetCode) /*** Note: T…

软件2班20240513

第三次作业 package com.yanyu;import java.sql.*; import java.util.ResourceBundle;public class JDBCTest01 {public static void main(String[] args) {ResourceBundle bundle ResourceBundle.getBundle("com/resources/db");// ctrl alt vString driver …

Unity打开安卓设备不同的设置面板

1,打开安卓设备不同的设置面板,我还贴心的把Android官网的链接放下面了 2,使用也很方便:unity按钮事件上拖这个脚本,注册MyOpenAndroidSettings方法,参数 填 和枚举值相应的数字 // 功能:打开…

贪吃蛇游戏(C语言实现)

目录 游戏效果展示文件代码的展示test.cSnake.cSnake.h 下一个坐标不是食物 游戏效果展示 QQ录屏20240507163633 文件 代码的展示 test.c #define _CRT_SECURE_NO_WARNINGS#include<locale.h> //设置本地化 #include"Snake.h"//游戏的测试逻辑 void test() {…

2024最佳项目管理软件整理

在项目管理领域&#xff0c;选择合适的任务管理软件对于提高团队效率和确保项目顺利进行至关重要。 以下是一些优秀的项目任务管理软件&#xff0c;以及它们的官网地址和特点介绍 序号软件名称官网地址特点介绍1zz-planhttps://zz-plan.com/一款在线甘特图协作软件&#xff0c…

c# - - - winform程序四个角添加圆角效果

winform 给窗体四个角添加圆角效果。 在窗体 Load 事件中添加如下代码&#xff1a; // 创建了一个圆角矩形的路径&#xff0c;并将其设置为控件的形状 System.Drawing.Drawing2D.GraphicsPath path new System.Drawing.Drawing2D.GraphicsPath(); int radius 30; path.AddAr…

ssm123基于java web的网上书城系统的设计与实现+vue

基于java web的网上书城系统的设计与实现vue 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;商品交易当然也不能排除在外&#xff0c;随着商品交易管理的不断成熟&#xff0c;它彻底改变了…

基于FPGA的视频矩阵切换方案

一、单个显示设备的系统方案&#xff1a;会议室只有1个显示设备 会议室的信号源有很多&#xff0c;但是显示设备只有1个&#xff0c;这个时候最佳方案是使用切换器。 &#xff08;1&#xff09;切换器&#xff08;控制方式&#xff1a;遥控器、软件、机箱面板、中控&#xff…

DS高阶:B树系列

一、常见的搜索结构 1、顺序查找 时间复杂度&#xff1a;O(N) 2、二分查找 时间复杂度&#xff1a;O(logN) 要求&#xff1a;&#xff08;1&#xff09;有序 &#xff08;2&#xff09;支持下标的随机访问 3、二叉搜索树&#xff08;BS树&#xff09; 时间复杂…

外卖系统微信小程序支付

微信小程序支付时序图 其中第9.步骤就是微信小程序前端调用wx.requestPayment