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

【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

 

目录

一.【Leetcode206】反转链表

1.链接

2.题目再现

 3.解法A:三指针法

二.【Leetcode21】合并两个有序链表

1.链接

2.题目再现

 3.三指针尾插法

三.【Leetcode160】相交链表

1.链接

2.题目再现

3.解法

四.链表的回文结构

1.链接

2.题目再现

 3.解法


一.【Leetcode206】反转链表

1.链接

反转链表

2.题目再现

 3.解法:三指针法

1.定义三个指针n1 n2 n3,n1指向空,n2指向头节点,n3指向头节点的next

2.注意:要先判断是否是空链表

3.用n2遍历链表,n2为空时就跳出循环

4.翻转链表,即n2->next=n1;

5.翻转下一个节点,即n1=n2;n2=n3;n3=n3->next;

6.注意:在n3=n3->next前要先判断n3是否为空,若为空就结束循环,否则可能会发生对空指针的解引用;

7.n1为反转后的头节点,返回n1。

动态演示:

三指针动态演示

代码:

struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL)return NULL;struct ListNode*n1=NULL;struct ListNode*n2=head;struct ListNode*n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3==NULL)break;n3=n3->next;}return n1;
}

二.【Leetcode21】合并两个有序链表

1.链接

合并两个有序链表

2.题目再现

 3.三指针尾插法

思路:创建一个新的链表,分别遍历两个链表,小的就尾插到新链表,然后指针向后走一步,直到有一方为空时就结束循环;结束循环后,判断哪个链表不为空,把不为空的尾插到新链表中去。

1.定义指针cur1=list1,cur2=list2,建立新的链表newlist,和保存新链表尾节点的指针tail;

2.注意:在遍历前要先判断两链表是否为空,若一方为空,则直接返回另一方;

3.分表遍历两个链表,比较其值,小的尾插到新链表,并向后走一步(如果一样大,那么随便取哪一个都行);

4.结束循环后,判断哪个链表不为空,尾插到新链表。

动态演示:

合并两个有序链表动态演示

代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode*newlist=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*cur1=list1;struct ListNode*cur2=list2;struct ListNode*tail=newlist;//newlist->next=tail;while(cur1&&cur2){if(cur1->val<cur2->val){tail->next=cur1;tail=tail->next;cur1=cur1->next;}else{tail->next=cur2;tail=tail->next;cur2=cur2->next;}}if(cur1){tail->next=cur1;}if(cur2){tail->next=cur2;}struct ListNode*head=newlist->next;free(newlist);newlist=NULL;return head;}

三.【Leetcode160】相交链表

1.链接

相交链表

2.题目再现

3.解法

1.先分别遍历两个链表,记录下两个链表的长度;

2.如果两个链表尾节点的地址一样,则说明它们相交,否则不相交,(注意是地址不是值);

3.求出两个链表长度的差gap

4.先让长的链表走差距步gap,短的链表先不动;

5.然后两个链表同时走一步,比较每走一步时两个链表当前节点的地址,如果一样,则说明找到了它们相交的起始位置,返回。 

动态演示:

相交链表动态演示

代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode*tailA=NULL;struct ListNode*tailB=NULL;int n1=0,n2=0;struct ListNode*cur1=headA,*cur2=headB;while(cur1){n1++;tailA=cur1;cur1=cur1->next;}while(cur2){n2++;tailB=cur2;cur2=cur2->next;}if(tailA!=tailB)return NULL;int gap=n1-n2;if(gap<0)gap=-gap;struct ListNode*longlist=headA,*shortlist=headB;if(n1<n2){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}   while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

四.链表的回文结构

1.链接

链表的回文结构

2.题目再现

 3.解法

首先我们得知道什么是回文结构?

简单来说,回文结构不管是正着读还是倒着读,结果是一样的;

我们就可以利用这一点来解决这道题。

1.找到链表的中间节点;

2.逆置链表中间节点以后的部分,rmid 为后半部分逆置后的第一个节点;

3.头指针 head 和 rmid 同时向后遍历,若 head 的值不等于 rmid 的值,则不是回文结构,返回 false ,循环结束后则是回文结构,返回 true 。

动态演示:

回文链表动态演示

代码:

struct ListNode* middleNode(struct ListNode* head)   //找中间节点
{struct ListNode*slow=head;struct ListNode*fast=head;while(fast){//slow=slow->next;if(fast->next==NULL){break;}else{fast=fast->next->next;}slow=slow->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=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3==NULL)break;n3=n3->next;}return n1;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* head) {// write code herestruct ListNode*mid=middleNode(head);struct ListNode*rmid=reverseList(mid);while(head&&rmid)   //分别遍历{if(head->val!=rmid->val)  //不相等则返回 false{return false;}head=head->next;rmid=rmid->next;}return true;}
};

😽本篇文章到此就结束了,若有错误或是建议,欢迎小伙伴们指出;😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃

程序员的自我修养

 

相关文章:

【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

目录 一.【Leetcode206】反转链表 1.链接 2.题目再现 3.解法A&#xff1a;三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现 3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现 3.解法 一.…...

M1、M2芯片Mac安装虚拟机

目录前言一、安装二、网络设置三、连接SSH客户端前言 一直想着给M1 Mac上安装虚拟机&#xff0c;奈何PD收费&#xff0c;找的破解也不稳定&#xff0c;安装上镜像就起不来。 注&#xff1a;挂长久的分享莫名其妙被封&#xff0c;需要安装包请私信我。 一、安装 虚拟机选择&a…...

算法刷题-只出现一次的数字、输出每天是应该学习还是休息还是锻炼、将有序数组转换为二叉搜索树

只出现一次的数字&#xff08;位运算、数组&#xff09; 给定一个非空整数数组&#xff0c;除了某个元素只出现一次以外&#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。 说明&#xff1a; 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗&…...

详解专利对学生、老师和企业员工、创业者、积分落户、地方补助的好处

大家好,我是英子老师。作为一名知识产权专家,深耕于专利行业十余年,具有丰富的专利工作经验:曾在大型专利代理机构从事专利代理工作、专利质检工作(抽查代理机构的专利代理人的撰写质量并评分);之后在知名上市企业、行业龙头企业担任高级专利工程师的职位,主要工作内容…...

Python图像处理:频域滤波降噪和图像增强

图像处理已经成为我们日常生活中不可或缺的一部分&#xff0c;涉及到社交媒体和医学成像等各个领域。通过数码相机或卫星照片和医学扫描等其他来源获得的图像可能需要预处理以消除或增强噪声。频域滤波是一种可行的解决方案&#xff0c;它可以在增强图像锐化的同时消除噪声。 …...

智能手机高端“酣战”,转机在何方?

经过多年发展&#xff0c;如今全世界有七成手机由中国制造&#xff0c;但在利润最丰厚的高端市场&#xff0c;国产厂商在很长一段时间之内都是形单影只&#xff0c;曾经一度跻身高端的“华为”因为封禁成了“绝唱”。 华为“失声”高端之后&#xff0c;其他一众国产厂商或主动…...

K8s pod 动态弹性扩缩容 HPA

一、概述Horizontal Pod Autoscaler&#xff08;HPA&#xff0c;Pod水平自动伸缩&#xff09;&#xff0c;根据平均 CPU 利用率、平均内存利用率或你指定的任何其他自定义指标自动调整 Deployment 、ReplicaSet 或 StatefulSet 或其他类似资源&#xff0c;实现部署的自动扩展和…...

C++中的类简要介绍

文章目录前言一、什么是类什么是对象1.类的概述2.对象的概述二、如何创建使用类三、class和struct创建类时的区别1.访问级别2.继承方式总结前言 本篇文章讲给大家介绍一个C中重要的概念&#xff0c;了解了这个概念大家就明白了为什么C会叫做面向对象编程了。 一、什么是类什么…...

项目管理工具DHTMLX Gantt灯箱元素配置教程:只读模式

DHTMLX Gantt是用于跨浏览器和跨平台应用程序的功能齐全的Gantt图表。可满足项目管理应用程序的大部分开发需求&#xff0c;具备完善的甘特图图表库&#xff0c;功能强大&#xff0c;价格便宜&#xff0c;提供丰富而灵活的JavaScript API接口&#xff0c;与各种服务器端技术&am…...

从LiveData迁移到Kotlin的 Flow,才发现是真的香!

LiveData 对于 Java 开发者、初学者或是一些简单场景而言仍是可行的解决方案。而对于一些其他的场景&#xff0c;更好的选择是使用 Kotlin 数据流 (Kotlin Flow)。虽说数据流 (相较 LiveData) 有更陡峭的学习曲线&#xff0c;但由于它是 JetBrains 力挺的 Kotlin 语言的一部分&…...

【BOOST C++】组件编程(2)-- 组件的设计原理

GitHub - ros2/demos at foxy 一、说明 为了研究ROS2的组件编程&#xff0c;首先要理解如何何为组件。组件本是微软的发明物体&#xff0c;但是在ubuntu上需要自己从底层实现&#xff0c;就说ROS2不用你写&#xff0c;但是就能看明白也是需要一点理论功底的。本篇按照COM内幕的…...

基于单细胞多组学数据无监督构建基因调控网络

在单细胞分辨率下识别基因调控网络&#xff08;GRNs&#xff0c;gene regulatory networks&#xff09;一直是一个巨大的挑战&#xff0c;而单细胞多组学数据的出现为构建GRNs提供了机会。 来自&#xff1a;Unsupervised construction of gene regulatory network based on si…...

蓝桥杯-最优清零方案(2022省赛)

蓝桥杯-最优清零方案1、问题描述2、解题思路3、代码实现1、问题描述 给定一个长度为 N 的数列 1,2,⋯,A1,A2,...,ANA_1,A_2,...,A_NA1​,A2​,...,AN​ 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。 每次操作小蓝可以选择以下两种之一: 1. 选择一个大于 0 的整数, 将…...

Mac免费软件下载网站推荐(最全免费,替代MacWk)

一、Appstorrent 官方网站&#xff1a; https://appstorrent.ru/ 这是一个俄语网站&#xff0c;其他很多网站资源都来自这里。点击右上角切换到中文。不需要登录网站&#xff0c;直接从软件详情页下载即可。体验非常好。 二、Xclient 官方网站&#xff1a; https://xclie…...

GPU是什么

近期ChatGPT十分火爆&#xff0c;随之而来的是M国开始禁售高端GPU显卡。M国想通过禁售GPU显卡的方式阻挡中国在AI领域的发展。 GPU是什么&#xff1f;GPU&#xff08;英语&#xff1a;Graphics Processing Unit&#xff0c;缩写&#xff1a;GPU&#xff09;是显卡的“大脑”&am…...

20230305学习计划

目录 第二天学习开发框架 前言 一、巩固复习第一天20230304学习笔记 二、SpringMVC中的控制器是不是单例模式&#xff1f;如果是&#xff0c;如何保证线程安全&#xff1f; 1、控制器是单例模式&#xff0c;是线程不安全的。 2、Spring中保证线程安全的方法&#xff1a; …...

SocketCan 应用编程

SocketCan 应用编程 由于 Linux 系统将 CAN 设备作为网络设备进行管理&#xff0c;因此在 CAN 总线应用开发方面&#xff0c;Linux 提供了SocketCAN 应用编程接口&#xff0c;使得 CAN 总线通信近似于和以太网的通信&#xff0c;应用程序开发接口更加通用&#xff0c;也更加灵…...

从零学习python - 04函数方法与返回值

函数&#xff1a;Function-也称为方法&#xff0c;是组织好的、可重复使用的&#xff0c;用来实现指定功能的代码块。函数的定义与调用:创建函数目的是封装业务逻辑&#xff0c;实现代码复用# 创建函数关键字:def(definition)def fun1(x, y):print(x y)函数的参数:python函数中…...

MySQL实战之事务到底是隔离的还是不隔离的

1.前言 我们在MySQL实战之事务隔离&#xff1a;为什么你改了我还看不见讲过事务隔离级别的时候提到过&#xff0c;如果是可重复读隔离级别&#xff0c;事务T启动的时候会创建一个视图read-view,之后事务T执行期间&#xff0c;即使有其他事务修改了数据&#xff0c;事务T看到的…...

Elasticsearch:理解 Master,Elections,Quorum 及 脑裂

集群中的每个节点都可以分配多个角色&#xff1a;master、data、ingest、ml&#xff08;机器学习&#xff09;等。 我们在当前讨论中感兴趣的角色之一是 master 角色。 在 Elasticsearch 的配置中&#xff0c;我们可以配置一个节点为 master 节点。master 角色的分配表明该节点…...

独立开发者如何下载使用Taotoken管理多个AI项目的模型与密钥

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 独立开发者如何下载使用Taotoken管理多个AI项目的模型与密钥 对于独立开发者或小型工作室而言&#xff0c;同时推进多个AI应用项目…...

JPlag代码抄袭检测工具:如何高效识别17种编程语言的代码抄袭行为

JPlag代码抄袭检测工具&#xff1a;如何高效识别17种编程语言的代码抄袭行为 【免费下载链接】JPlag State-of-the-Art Source Code Plagiarism & Collusion Detection. Check for plagiarism in a set of programs. 项目地址: https://gitcode.com/gh_mirrors/jp/JPlag …...

如何解决Funannotate数据库安装失败:从403错误到完整部署的实战指南

如何解决Funannotate数据库安装失败&#xff1a;从403错误到完整部署的实战指南 【免费下载链接】funannotate Eukaryotic Genome Annotation Pipeline 项目地址: https://gitcode.com/gh_mirrors/fu/funannotate Funannotate是真核基因组注释的强大工具&#xff0c;但在…...

技术突破开源方案:img2latex-mathpix实现公式图像转LaTeX代码的本地化部署

技术突破开源方案&#xff1a;img2latex-mathpix实现公式图像转LaTeX代码的本地化部署 【免费下载链接】img2latex-mathpix Mathpix has changed their billing policy and no longer has free monthly API requests. This repo is now archived and will not receive any upda…...

告别龟速下载!实测对比Axel、Aria2、mwget三大神器,教你选对多线程工具

三大命令行下载神器深度横评&#xff1a;Axel、Aria2与mwget的性能对决 当你在终端里反复输入wget或curl命令&#xff0c;盯着缓慢增长的进度条时&#xff0c;是否想过还有更高效的解决方案&#xff1f;本文将带你深入探索Axel、Aria2和mwget这三款命令行下载加速工具&#xff…...

开源工具LMAO:通过浏览器自动化免费调用ChatGPT与Copilot API

1. 项目概述与核心价值如果你和我一样&#xff0c;是个喜欢折腾各种AI工具&#xff0c;但又对官方API的付费门槛、调用限制或者复杂的申请流程感到头疼的开发者&#xff0c;那么今天聊的这个项目&#xff0c;你一定会感兴趣。它叫LLM-API-Open&#xff0c;圈内朋友喜欢叫它LMAO…...

苍穹外卖开发日记-员工管理与AOP自动填充

苍穹外卖开发日记&#xff1a;员工管理、分类管理与AOP自动填充实战今天完成了苍穹外卖项目的员工管理模块、分类管理模块&#xff0c;并通过自定义注解AOP的方式实现了公共字段的自动填充&#xff0c;让我们来回顾一下这些核心功能的实现。一、今日工作概览时间完成内容14:44新…...

Jentic Mini:为AI智能体构建安全的API执行层与凭据管理方案

1. 项目概述&#xff1a;为AI智能体构建安全的API执行层 如果你正在开发AI智能体&#xff0c;并且希望它能帮你操作Notion、Slack、GitHub这些真实世界的服务&#xff0c;那你一定遇到过这个核心难题&#xff1a;怎么把API密钥安全地交给它&#xff1f;直接把密钥塞进提示词里&…...

LVGL图片资源全解析:从C数组到图标字体的高效集成方案

1. LVGL图片资源方案概述 在嵌入式GUI开发中&#xff0c;图片资源的管理直接影响产品性能和开发效率。LVGL作为轻量级图形库&#xff0c;提供了三种主流的图片集成方案&#xff1a;内部C数组、外部文件系统图片和图标字体。每种方案都有其独特的适用场景和实现方式&#xff0c;…...

告别环境报错!保姆级教程:从JRE到STM32CubeMX 6.10.0的完整安装与配置

从零搭建STM32开发环境&#xff1a;CubeMX 6.10.0避坑全指南 刚拿到STM32开发板时的兴奋&#xff0c;往往在环境配置阶段就被各种报错消磨殆尽。作为过来人&#xff0c;我深刻理解那种看着红色错误提示却无从下手的挫败感。本文将带你用最稳妥的方式完成从Java环境到CubeMX的全…...