链表OJ题(4)

目录

10.链表的回文结构

11.随机链表的复制


🙂找中间节点一定要考虑偶数个和奇数个的问题。

🙂指针指向的前中后。

🙂链表节点的位置个数/链表的节点中的数字。🆗🆗

今天最后两道链表OJ题目。

10.链表的回文结构

描述

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

测试样例: 


 【快慢指针中间节点+逆置链表+比较链表】

  • 先找到链表的中间节点(分奇偶)
  • 逆置后半段链表
  • 两个指针比较两个链表
  • 结束条件,某个指正为NULL就结束
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {//找中间节点ListNode*slow=A;ListNode*fast=A;while(fast->next && fast){fast=fast->next->next;slow=slow->next;}//逆置后半段链表ListNode*head=slow;ListNode*rhead=NULL;ListNode*cur=head;ListNode*tail=NULL;while(cur){ListNode*tmp=cur->next;if(rhead == NULL){rhead=tail=cur;rhead->next=NULL;}else {rhead=cur;rhead->next=tail;tail=rhead;}cur=tmp;}//比较rheadwhile(rhead && A){if(rhead->val != A->val){return false;}rhead=rhead->next;A=A->next;}return true;}};


11.随机链表的复制(链表的深度拷贝)

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码  接受原链表的头节点 head 作为传入参数。

示例一: 

 

 示例二:


【 尾插+某个位置插入】

  • 这道题目的综合性还挺强的,大家一定要把前面链表的知识扎根。才能轻易上手。
  • 单链表+随机链表(随机链表可以指向其他任何链表包括自己)
/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) 
{//第一步struct Node*cur=head;while(cur){struct Node*copy=(struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next=cur->next;cur->next=copy;cur=cur->next->next;}//第二步cur=head;while(cur){struct Node*copy=cur->next;if(cur->random == NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=cur->next->next;}//第三步cur=head;struct Node*newhead=NULL;struct Node*tail=NULL;while(cur){struct Node*copy=cur->next;if(newhead == NULL){newhead=tail=cur->next;}else{tail->next=cur->next;tail=tail->next;}cur->next=copy->next;cur=cur->next->next;}return newhead;
}//❌

 


 【找具体位置第几个】

但是这个方法的时间复杂度是O(N^2),时间复杂度是非常高的,建议学会上面的方法。 

12.链表逆置(头插)和链表顺序(尾插) 

【头插】 

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode*newhead=NULL;struct ListNode*cur=head;while(cur){struct ListNode*tmp=cur->next;cur->next=newhead;newhead=cur;cur=tmp;}return newhead;
}

【尾插】

struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode* cur=head;struct ListNode* tail=NULL;struct ListNode* newhead=NULL;while(cur){if(cur->val != val){if(tail){tail->next=cur;//易错tail=tail->next;}//处理头else{newhead=tail=cur;//易错}cur=cur->next;}else{struct ListNode* tmp=cur->next;free(cur);cur=tmp;}}//处理尾if(tail){tail->next=NULL;}return newhead;
}

最近天气渐冷,大家要注意保暖哦。

代码---------→【唐棣棣 (TSQXG) - Gitee.com】

联系---------→【邮箱:2784139418@qq.com】

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

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

相关文章

【C++】非类型模板参数 | array容器 | 模板特化 | 模板为什么不能分离编译

目录 一、非类型模板参数 二、array容器 三、模板特化 为什么要对模板进行特化 函数模板特化 补充一个问题 类模板特化 全特化与偏特化 全特化 偏特化 四、模板为什么不能分离编译 为什么 怎么办 五、总结模板的优缺点 一、非类型模板参数 模板参数分两类&#x…

数据结构预算法--链表(单链表,双向链表)

1.链表 目录 1.链表 1.1链表的概念及结构 1.2 链表的分类 2.单链表的实现(不带哨兵位) 2.1接口函数 2.2函数的实现 3.双向链表的实现(带哨兵位) 3.1接口函数 3.2函数的实现 1.1链表的概念及结构 概念:链表是一种物理存储结…

黑豹程序员-架构师学习路线图-百科:Knife4j API接口文档管理

文章目录 由来:接口文档第一代:Swagger第二代:Knife4j界面 由来:接口文档 古老编程是一个语言前后端通吃,ASP、JSP、PHP都是如此。 但随着项目规模变大,项目团队也开始壮大,岗位职责开始细分&a…

如何从零开始手写一个消息中间件(从宏观角度理解消息中间件的技术原理)

如何从零开始手写一个消息中间件(从宏观角度理解消息中间件的技术原理) 什么是消息中间件消息中间件的作用逐一拆解消息中间件的核心技术消息中间件核心技术总览IOBIONIOIO多路复用AIOIO多路复用详细分析selectpollepoll Java中的IO多路复用 协议序列化消…

【halcon】halcon 函数文件 以及 脚本引擎如何调用外部函数文件 上篇

前言 halcon有几种文件: 本地程序函数(.hdev)外部函数文件(.hdvp)库函数(.hdp) 说多了容易混淆,今天就说,我觉得最有用的:外部函数文件(.hdvp) 步骤 先写一段halcon脚本&#x…

Nuxt.js——基于 Vue 的服务端渲染应用框架

文章目录 前言一、知识普及什么是服务端渲染什么是客户端渲染?服务端渲染与客户端渲染那个更优秀? 二、Nuxt.js的特点Nuxt.js的适用情况? 三、Vue是如何实现服务端渲染的?安装依赖使用vue安装 Nuxt使用npm install安装依赖包使用n…

C语言——打印1000年到2000年之间的闰年

闰年&#xff1a; 1、能被4整除不能被100整除 2、能被400整除 #define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h> int main() {int year;for(year 1000; year < 2000; year){if((year%4 0) && (year%100!0) || (year%400 0)){printf("%d ",ye…

Java学习_对象

对象在计算机中的执行原理 类和对象的一些注意事项 this关键字 构造器 构造器是一种特殊的方法 : 特殊之处在于&#xff0c;名字必须与所在类的名字一样&#xff0c;而且不能写返回值类型 封装 封装的设计规范&#xff1a;合理隐藏、合理暴露 实体类 成员变量和局部变量的区别 …

vite基础学习笔记:14.路由跳转(二)携带query参数

说明&#xff1a;自学做的笔记和记录&#xff0c;如有错误请指正 1. 路由跳转&#xff08;携带query参数&#xff09; &#xff08;1&#xff09;第一层路由&#xff08;点击卡片路由跳转至新页面-携带query参数&#xff09; 知识点&#xff1a; query传参对应的是path和qu…

vscode 终端进程启动失败: shell 可执行文件“C:\Windows\System32\WindowsPower

vscode 终端进程启动失败: shell 可执行文件“C:\Windows\System32\WindowsPower 第一次用vscode&#xff0c;然后遇到这个问题&#xff0c;在设置里搜索 terminal.integrated.defaultProfile.windows 将这里的null改成"Command Prompt" 重启就可以了

【Git】深入了解Git及其常用命令

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Git的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.Git是什么 二.SVN和Git的区别 三.Git的…

通过SD卡给某摄像头植入可控程序

0x01. 摄像头卡刷初体验 最近研究了手上一台摄像头的sd卡刷机功能&#xff0c;该摄像头只支持fat32格式的sd卡&#xff0c;所以需要先把sd卡格式化为fat32&#xff0c;另外微软把fat32限制了最大容量32G&#xff0c;所以也只能用不大于32G的sd卡来刷机。 这里使用32G的sd卡来…

docker-compose安装es以及ik分词同义词插件

目录 1 前言 2 集成利器Docker 2.1 Docker环境安装 2.1.1 环境检查 2.1.2 在线安装 2.1.3 离线安装 2.2 Docker-Compose的安装 2.2.1 概念简介 2.2.2 安装步骤 2.2.2.1 二进制文件安装 2.2.2.2 离线安装 2.2.2.3 yum安装 3 一键安装ES及Kibana 3.1 yml文件的编写…

【Redis系列】Redis的核心命令(上)

哈喽&#xff0c;大家好&#xff0c;我是小浪。那么上篇博客教会了大家如何在Linux上安装Redis&#xff0c;那么本篇博客就要正式开始学习Redis啦&#xff0c;跟着俺的随笔往下看~ 1、启动Redis 那么如何启动Redis呢&#xff1f;最常用的是以下这个命令&#xff1a; redis-cl…

堆的应用-----Top k 问题

目录 前言 Topk问题 1.问题描述 2.解决方法 3.代码实现&#xff08;C/C&#xff09; 前言 在人工智能算法岗位的面试中&#xff0c;TopK是问得最多的几个问题之一&#xff1a; 到底有几种方法&#xff1f; 这些方案里蕴含的优化思路究竟是怎么样的&#xff1f; 为啥T…

如何用Excel软件制作最小二乘法①

一、用自带的选项&#xff08;不推荐&#xff09;&#xff0c;因为感觉只是近似&#xff0c;虽然结果一样 1.在Excel中输入或打开要进行在excel中输入或打开要进行最小二乘法拟合的数据&#xff0c;如图所示。 2.按住“shift”键的同时&#xff0c;用鼠标左键单击以选择数据&a…

电路综合-基于简化实频的SRFT集总参数切比雪夫低通滤波器设计

电路综合-基于简化实频的SRFT集总参数切比雪夫低通滤波器设计 6、电路综合-基于简化实频的SRFT微带线切比雪夫低通滤波器设计中介绍了使用微带线进行切比雪夫滤波器的设计方法&#xff0c;在此对集总参数的切比雪夫响应进行分析。 SRFT集总参数切比雪夫低通滤波器综合不再需要…

typora保护机制与注册逆向分析

、起因 一直比较喜欢Typora的简洁与美观&#xff08;尝试过用 vscode 搭配插件编辑 markdown 文件&#xff0c;体验还是要差一些的&#xff09;&#xff0c;突然发现自己windows机器上很久前安装的typora不让用了&#xff0c;提示&#xff1a; 幸好原始安装文件还在&#xf…

ASP.NETWeb开发(C#版)-day1-C#基础+实操

目录 .NET实操&#xff1a;创建项目执行 C#基础语法数据类型变量实操001_变量如何在一个解决方案 中创建另一个项目实操002结构实操003-if else实操004-多分支多行注释按钮实操&#xff1a;循环 面向对象基础如何在同一个项目下创建新的.cs文件实操-类的定义与访问实操-练习实操…

55基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲(椒盐)噪声

基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲&#xff08;椒盐&#xff09;噪声五组噪声模型&#xff0c;程序已调通&#xff0c;可直接运行。 55高斯噪声、瑞利噪声 (xiaohongshu.com)