LeetCode/NowCoder-链表经典算法OJ练习3

  孜孜不倦:孜孜:勤勉,不懈怠。指工作或学习勤奋不知疲倦。💓💓💓

目录

说在前面

题目一:返回倒数第k个节点

题目二:链表的回文结构

题目三:相交链表

SUMUP结尾


说在前面

 dear朋友们大家好!💖💖💖数据结构的学习离不开刷题,在对链表的相关OJ进行练习后又更新复杂度的OJ,这并不意味这链表的题目就结束了,我们今天就继续联系链表相关的OJ练习当今天我们的题目除了LeetCode,还来自NowCoder。

 👇👇👇

友友们!🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉


​以下是leetcode题库界面:

 👇👇👇

🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
​以下是NowCoder题库界面:

​​

 ​​

题目一:返回倒数第k个节点

题目链接:面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)

题目描述:

题目分析:

 思路1:将创建一个数组temp,将链表中节点的地址存入数组temp,再返回数组中下标为n-k的地址所指向的数据。

举例:1->2->3->4->5->6  和 k = 3

代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
#define numsSize 100
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;ListNode* temp[numsSize];//创建临时数组int i = 0;while (pcur != NULL)//将链表节点地址存入数组temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒数第k个节点的数据
}

不过,假设链表很长,此时空间复杂度就会比较高,所以用numsSize固定长度显然不是好的办法,应该用动态内存分配的办法来初始化temp

代码如下:

 /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;int length = 0;while (pcur != NULL)//遍历数组,得到节点的个数{length++;pcur = pcur->next;}//动态创建二级指针变量tempListNode** temp = (ListNode**)malloc(length * sizeof(ListNode*));pcur = head;int i = 0;while (pcur != NULL)//将链表节点地址存入temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒数第k个节点的数据
}

不过显然空间复杂度为O(N),不是一个非常好的办法。如果给出前提条件:空间复杂度为O(1),这个方法就不行了。

 思路2:将创快慢指针法:定义快慢指针fast、slow,先让fast走k步,再让slow和fast同时走,这样当fast走完slow刚好指向倒数第k个节点。

举例:1->2->3->4->5->6  和 k = 3

代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {//定义快慢指针ListNode* slow = head;ListNode* fast = head;while (k--)//让fast先走k步{fast = fast->next;}//当fast走完,此时slow指向的就是倒数第k个节点while (fast != NULL){fast = fast->next;slow = slow->next;}return slow->val;
}

 ​​

题目二:链表的回文结构

题目链接:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

题目描述:

题目分析:

 思路:先找到链表的中间节点,再将链表的后半部分反转,比较前半部分和后半部分的元素是否相等。

我们需要用到之前OJ练习1中的两个函数:


1.链表的中间节点:876. 链表的中间结点 - 力扣(LeetCode)

2.反转链表:206. 反转链表 - 力扣(LeetCode)

如果忘记了,大家点击这里复习:LeetCode/NowCoder-链表经典算法OJ练习1

代码如下:

/*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;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反转链表struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}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;A = A->next;}return true;}
};

像这种题属于组合体,比较综合,同时也告诉我们具有一定功能的代码在下次使用时可以稍加修改再Ctrl+C/V,可以省去很多麻烦,也比较方便。  

 ​​

题目三:相交链表

题目链接:160. 相交链表 - 力扣(LeetCode)

题目描述:

题目分析:

思路:这题比较复杂,我们需要模块化思考。同时注意单链表相交为"Y"型而不可能为"X"型,因为单链表没有两个next指针。

1、如何判断相交?

判断尾指针,如果尾指针地址相同则相交(注意,不能用尾节点所存储的值是否相同判断,因为之前有可能也有节点存储了和尾节点相同的值)。

2、若相交,如何找出第一个交点?

思路1:A链表的节点依次和B链表的所有节点比较,A的某个节点和B链表的某个节点相等,则这个节点就是交点。

 代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* cur1 = headA;ListNode* cur2 = headB;//让A、B链表都走到尾节点while(cur1->next){cur1 = cur1->next;}while(cur2->next){cur2 = cur2->next;}if(cur1 != cur2)//判断尾节点是否相等return NULL;cur1 = headA;while(cur1->next)//让A中每个节点都和B中的所有节点比较{cur2 = headB;while(cur2->next){if(cur1 == cur2)//第一个相等的就是交点return cur2;cur2 = cur2->next;}cur1 = cur1->next;}   return cur2;
}

这个方法的时间复杂度为O(N^2)

思路2:分别计算出链表A、B的长度,让长的先走差距的步数,然后再让两链表同时开始走,第一个相等的就是交点。

代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {ListNode* cur1 = headA, * cur2 = headB;int lenA = 0;int lenB = 0;while (cur1->next)//统计链表A的长度{lenA++;cur1 = cur1->next;}while (cur2->next)//统计链表B的长度{lenB++;cur2 = cur2->next;}if (cur1 != cur2)//判断是否有交点return NULL;//假设法,设置长短链表ListNode* LongList = headA, * ShortList = headB;if (lenA < lenB){LongList = headB;ShortList = headA;}int gap = abs(lenA - lenB);//两链表节点差值while (gap--)//让长的先走差值的步数{LongList = LongList->next;}while (LongList != ShortList)//让两链表一起走,第一个相等的就是交点{LongList = LongList->next;ShortList = ShortList->next;}return LongList;
}

这个方法的时间复杂度为O(N)

对比两种解法,显然第二种方法是更好的。 

 

SUMUP结尾

数据结构就像数学题,需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题,希望大家一起学习,共同进步~

如果大家觉得有帮助,麻烦大家点点赞,如果有错误的地方也欢迎大家指出~

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

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

相关文章

K-means聚类算法详细介绍

目录 &#x1f349;简介 &#x1f348;K-means聚类模型详解 &#x1f348;K-means聚类的基本原理 &#x1f348;K-means聚类的算法步骤 &#x1f348;K-means聚类的优缺点 &#x1f34d;优点 &#x1f34d;缺点 &#x1f348;K-means聚类的应用场景 &#x1f348;K-mea…

全局查询筛选器适用场景 以及各场景示例

EF Core中的全局查询筛选器&#xff08;Global Query Filters&#xff09;是一种强大的功能&#xff0c;可以在实体框架的DbContext级别为特定的EntityType设置默认的过滤条件。这些筛选器自动应用于所有涉及到相关实体的LINQ查询中&#xff0c;无论是直接查询还是通过Include或…

借助 CloudFlare 增强站点内容保护防采集

今天在一位站长的帮助下实测了 CloudFlare 增强站点内容保护实现防采集的功能,效果那是杠杠的,如果您的站点原创内容比较多的话,明月强烈建议试试 CloudFlare 这个内容保护,无论是 WordPress 、Typecho 都有非常好的效果,并且几乎没有任何误伤,搜索引擎爬虫蜘蛛更是不会影…

利用边缘计算网关的工业设备数据采集方案探讨-天拓四方

随着工业4.0时代的到来&#xff0c;工业设备数据采集成为了实现智能制造、提升生产效率的关键环节。传统的数据采集方案往往依赖于中心化的数据处理方式&#xff0c;但这种方式在面对海量数据、实时性要求高的工业场景时&#xff0c;往往显得力不从心。因此&#xff0c;利用边缘…

内存泄漏案例分享3-view的内存泄漏

案例3——view内存泄漏 前文提到&#xff0c;profile#Leaks视图无法展示非Activity、非Fragment的内存泄漏&#xff0c;换言之&#xff0c;除了Activity、Fragment的内存泄漏外&#xff0c;其他类的内存问题我们只能自己检索hprof文件查询了。 下面有一个极佳的view内存泄漏例子…

数据结构——不相交集(并查集)

一、基本概念 关系&#xff1a;定义在集合S上的关系指对于a&#xff0c;b∈S&#xff0c;若aRb为真&#xff0c;则a与b相关 等价关系&#xff1a;满足以下三个特性的关系R称为等价关系 (1)对称性&#xff0c;aRb为真则bRa为真&#xff1b; (2)反身性,aRa为真; (3)传递性,aRb为真…

【程序员如何送外卖】

嘿&#xff0c;咱程序员要在美团送外卖&#xff0c;那还真有一番说道呢。 先说说优势哈&#xff0c;咱程序员那逻辑思维可不是盖的&#xff0c;规划送餐路线什么的&#xff0c;简直小菜一碟。就像敲代码找最优解一样&#xff0c;能迅速算出怎么送最省时间最有效率。而且咱平时…

“技术与管理并重:构建以等保测评为导向的全方位防御体系“

在数字化转型浪潮下&#xff0c;企业信息安全面临着前所未有的挑战。为了有效应对日益复杂的网络威胁&#xff0c;构建一个稳固的信息安全防线&#xff0c;技术手段与管理制度的有机结合显得尤为重要。本文将探讨如何以信息安全等级保护测评&#xff08;等保测评&#xff09;为…

【HUST】信道编码|基于LDPC码的物理层安全编码方案概述

本文对方案的总结是靠 Kimi 阅读相关论文后生成的&#xff0c;我只看了标题和摘要感觉确实是这么回事&#xff0c;并没有阅读原文。 行文逻辑&#xff1a;是我自己设定的&#xff0c;但我并不是这个研究领域的&#xff0c;所以如果章节划分时有问题&#xff0c;期待指出&#x…

音乐编曲软件哪个好用 studio one和fl studio哪个好

编曲软件的出现&#xff0c;打破了时间与空间的限制&#xff0c;使得创作者能随时随地进行音乐创作。随着信息时代的发展&#xff0c;使用编曲软件进行音乐创作已经成为业界主流。业内常用的有Cubsae、LogicPro、Studio One、Ableton live等&#xff0c;这次教程我将为大家解读…

云计算期末复习(1)

云计算基础 作业&#xff08;问答题&#xff09; &#xff08;1&#xff09;总结云计算的特点。 透明的云端计算服务 “无限”多的计算资源&#xff0c;提供强大的计算能力 按需分配&#xff0c;弹性伸缩&#xff0c;取用方便&#xff0c;成本低廉资源共享&#xff0c;降低企…

【全开源】填表统计预约打卡表单系统FastAdmin+ThinkPHP+UniApp

简化流程&#xff0c;提升效率 一、引言&#xff1a;传统表单处理的局限性 在日常工作和生活中&#xff0c;我们经常会遇到需要填写表单、统计数据和预约打卡等场景。然而&#xff0c;传统的处理方式往往效率低下、易出错&#xff0c;且不利于数据的统计和分析。为了解决这些…

OpenLayers6入门,OpenLayers实现在地图上拖拽编辑修改绘制图形

专栏目录: OpenLayers6入门教程汇总目录 前言 在前面一章中,我们已经学会了如何绘制基础的三种图形线段、圆形和多边形:《OpenLayers6入门,OpenLayers图形绘制功能,OpenLayers实现在地图上绘制线段、圆形和多边形》,那么本章将在此基础上实现图形的拖拽编辑功能,方便我…

如何使用Android NDK将头像变成“遗像”

看完本文的标题&#xff0c;可能有人要打我。你说黑白的老照片不好吗&#xff1f;非要说什么遗像&#xff0c;我现在就把你变成遗像&#xff01;好了&#xff0c;言归正传。我想大部分人都用过美颜相机或者剪映等软件吧&#xff0c;它们的滤镜功能是如何实现的&#xff0c;有人…

Amazon云计算AWS之[7]内容推送服务CloudFront

文章目录 CDNCDN简介CDN网络技术 CloudFrontCloudFront基本概念 CDN CDN简介 用户在发出服务请求后&#xff0c;需要经过DNS服务器进行域名解析后得到所访问网站的真实IP&#xff0c;然后利用该IP访问网站。在这种模式中&#xff0c;世界各地的访问者都必须直接和网站服务器连…

统计计算四|蒙特卡罗方法(Monte Carlo Method)

系列文章目录 统计计算一|非线性方程的求解 统计计算二|EM算法&#xff08;Expectation-Maximization Algorithm&#xff0c;期望最大化算法&#xff09; 统计计算三|Cases for EM 文章目录 系列文章目录一、基本概念&#xff08;一&#xff09;估算 π \pi π&#xff08;二&…

TS(TypeScript)中Array数组无法调出使用includes方法,显示红色警告

解决方法 打开tsconfig.json文件&#xff0c;添加"lib": ["es7", "dom"]即可。 如下图所示。

AWS安全性身份和合规性之Artifact

AWS Artifact是对您很重要的与合规性相关的信息的首选中央资源。AWS Artifact是一项服务&#xff0c;提供了一系列用于安全合规的文档、报告和资源&#xff0c;以帮助用户满足其合规性和监管要求。它允许按需访问来自AWS和在AWS Marketplace上销售产品的ISV的安全性和合规性报告…

探索k8s集群中kubectl的陈述式资源管理

一、k8s集群资源管理方式分类 1.1陈述式资源管理方式&#xff1a;增删查比较方便&#xff0c;但是改非常不方便 使用一条kubectl命令和参数选项来实现资源对象管理操作 即通过命令的方式来实 1.2声明式资源管理方式&#xff1a;yaml文件管理 使用yaml配置文件或者json配置文…

常见API(JDK7时间、JDK8时间、包装类、综合练习)

一、JDK7时间——Date 1、事件相关知识点 2、Date时间类 Data类是一个JDK写好的Javabean类&#xff0c;用来描述时间&#xff0c;精确到毫秒。 利用空参构造创建的对象&#xff0c;默认表示系统当前时间。 利用有参构造创建的对象&#xff0c;表示指定的时间。 练习——时间计…