【Java--数据结构】链表经典OJ题详解(上)

news/2024/5/5 17:24:44

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



目录

谈谈头插、头删、尾插、头插的时间复杂度

反转一个单链表 

链表的中间结点

返回倒数第k个结点

合并两个链表


谈谈头插、头删、尾插、头插的时间复杂度

头插和头删的时间复杂度为O(1),

尾插和尾删的时间复杂度为O(n) (因为尾插和尾删要一个个遍历完链表)

反转一个单链表 

OJ链接

采用头插法

创建cur指针使得cur=head.next

将head.next置空(作为尾节点)(注意要判断head为空的情况,return head,否则会报空指针异常)

  1. 创建curN指针使得curN=cur.next
  2. 让cur.next=head
  3. head=cur

1~3步是一个循环,进入循环条件是cur!=null(即当cur为空时,代表cur已经遍历完链表)


class Solution {public ListNode reverseList(ListNode head) {if(head==null){return head;}//正常情况ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curN=cur.next;cur.next=head;head=cur;cur=curN;}return head;}
}

链表的中间结点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结 点。OJ链接

 快慢指针法

定义一个慢指针slow(每次走一步),一个快指针fast(每次走两步)

  • 即slow=slow.next
  • fast=fast.next.next

这是一个循环,进入循环的条件为fast!=null&&fast.next!=null(这两个条件不可以交换,否则当fast=null时,先判断fast.next!=null时,会出现空指针异常)

fast!=null针对的是链表长度是数的情况

fast.next!=null针对的是链表长度是数的情况

class Solution {public ListNode middleNode(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}

返回倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点。OJ链接

 定义两个节点fast和slow,先让fast走k步,再让fast和slow一起走,当fast走完链表时,此时slow的位置就是倒数第k个节点。(fast和slow之间的距离就是k,当fast走到null时,返回slow.val)

 

fast先走k步,用count计数,

  • fast=fast.next
  • count++

这是一个循环,条件是count<k(count是从0开始的,所以count<k 就是让fast走了k 步)

接着让fast和slow一起走,进入循环条件是fast!=null

  • fast=fast.next
  • slow=slow.next
class Solution {public int kthToLast(ListNode head, int k) {ListNode fast=head;ListNode slow =head;int count=0;while(count<k){fast=fast.next;count++;}while(fast!=null){fast=fast.next;slow=slow.next;}return slow.val;}
}

合并两个链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ 链接

定义一个哨兵位节点newH,遍历节点tmp

比较A和B链表的值,谁小,就将谁的节点放入新链表中

若A的值小( B同理)

  • tmp.next=headA;
  • headA=headA.next;
  • tmp=tmp.next;

这是一个循环,进入循环条件是headA!=null&&headB!=null(只要有一个链表遍历完了,就跳出循环)

还要判断A走完,B还有的情况(headA=null),(反之同理)

tmp.next=headB;

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode headH=new ListNode();ListNode cur=headH;while(list1!=null&&list2!=null){if(list1.val<list2.val){             cur.next=list1;list1=list1.next;cur=cur.next;        }else{cur.next=list2;list2=list2.next;cur=cur.next;}}if(list1==null){cur.next=list2;}if(list2==null){cur.next=list1;}return headH.next;}
}


http://www.mrgr.cn/p/20728580

相关文章

顺序栈--代码题

数据结构 顺序栈代码题设计一个进制转换程序,使用顺序栈设计一个把十进制转化为十六进制的接口,实现当键盘输入一个非负的十进制时,可以在终端输出对应的十六进制数。 /***************************************************************************************** file n…

完美运营版商城/拼团/团购/秒杀/积分/砍价/实物商品/虚拟商品等全功能商城

源码下载地址&#xff1a;完美运营版商城.zip 后台可以自由拖曳修改前端UI页面 还支持虚拟商品自动发货等功能 挺不错的一套源码 前端UNIAPP 后端PHP 一键部署版本

aws安装jenkins步骤

一、aws安装jdk11 1.1 aws安装jdk11 1、切换root,更新yum, sudo su yum update exist 2、安装JDK1.8版本 yum -y list java-1.8.0* #(安装jdk11,yum -y list java-11*) yum install java-1.8.0-openjdk-devel.x86_64 #(安装jdk11,yum -y list java-11-openjdk-deve…

嵌入式4-24

作业&#xff1a; 整理思维导图 定义一个矩形类Rec&#xff0c;包含私有属性length&#xff0c;width&#xff0c;有以下成员函数&#xff1a; void set_length(int l); //设置长度 void set_width(int w); //设置宽度 int get_length(); //获取长度 int get_width(); //获取宽…

【GIS教程】ArcGIS做日照分析(附练习数据下载)

我国对住宅日照标准的规定是:冬至日住宅底层日照不少于1小时或大寒日住宅层日照不少于2小时(通常以当地冬至日正午12时的太阳高度角作为依据)。因冬至日太阳高度角最低&#xff0c;照射范围最小&#xff0c;如果冬至日12&#xff1a;00建筑物底层能够接收到阳光&#xff0c;那么…

Golang | Leetcode Golang题解之第42题接雨水

题目&#xff1a; 题解: func trap(height []int) (ans int) {n : len(height)if n 0 {return}leftMax : make([]int, n)leftMax[0] height[0]for i : 1; i < n; i {leftMax[i] max(leftMax[i-1], height[i])}rightMax : make([]int, n)rightMax[n-1] height[n-1]for i…

详解MySQL C API 相关接口(大白话就是:MySQL的c语言怎么写)

文章目录 1、C API 官方文档2、初始化 MYSQL3、连接 MySQL设置连接字符集&#xff08;使得客户端编码方式匹配&#xff09; 4、下发 mysql 指令5、获取 mysql 查询结果(保存起来)获取行与列遍历存储结果 6、释放 MYSQL\_RES 对象7、关闭 MySQL 连接8、总结 1、C API 官方文档 …

vue3 删除对象中的属性,可以使用js里的delete,但需注意ts定义对象类型!

如上如&#xff0c;当使用delete 删除stateData中的属性时&#xff0c; 报错&#xff0c;意思为 TypeScript 错误“‘delete’ 运算符的操作数必须是可选的 什么原因呢&#xff1f;是因为我偷懒 缺少了ts定义类型 方法一&#xff1a; &#xff08;不推荐&#xff09; delete …

嵌入式笔记4.1 GPIO 功能复用

目录一、了解 MCU(GPIO)具有的所有复用功能通过查看 MCU 的数据手册可以知道 MCU 的所有引脚的功能:例 STM32L431:例 stm32f103:复用、重映射、多路复用(多功能引脚)GPIO复用(AF - Alternate Function)重映射(Remapping)多路复用(Multi-function)常见引脚功能一览…

【八股】Redisson分布式锁

Redisson分布式锁 主要了解了Redisson分布式锁实现的三个功能&#xff1a; 1.可重入 -> 防止死锁 2.可重试&#xff08;i.e. 非阻塞获取锁&#xff09; 3.自动续约 1. 可重入 原理&#xff1a; 利用Redis的Hash结构&#xff0c;记录了使用当前锁的线程id和重用次数&#…

如何分析和优化慢sql语句

前言 sql查询速度比较慢容易成为性能瓶颈,这时我们可以优化我们的sql语句或数据库表 一般sql语句执行很慢的种类分为: 1.聚合查询 2.多表查询 3.表数据量过大查询 4.深度分页查询 这四种的前三种都可以通过优化sql语句来优化sql查询速度 正文 聚合查询 我们可以通过尝…

初始C++

1. C关键字(C98) C总计63个关键字&#xff0c; C语言32个关键字 ps&#xff1a;下面我们只是看一下C有多少关键字&#xff0c;不对关键字进行具体的讲解。后面我们学到以后再 细讲。 2. 命名空间 在C/C中&#xff0c;变量、函数和后面要学到的类都是大量存在的&#xff0c;…

ps/lr如何为一个型号相机的raw使用其他相机的预设

首先单独下载camera raw,进到C:\ProgramData\Adobe\CameraRaw\CameraProfiles\Camera中获取想要的相机型号的预设dcp文件 去 https://liquidtelecom.dl.sourceforge.net/project/dcptool/dcptool/dcpTool V1.11.0/dcpTool_1_11_0.zip?viasf=1 下载dcp编译工具dcpTool cd C:\U…

Oracle 21 C 安装详细操作手册,并配置客户端连接

Oracle 21 C 安装详细操作手册 Win 11 Oracle 21C 下载&#xff1a; Database Software Downloads | Oracle 中国 云盘共享 链接&#xff1a;https://pan.baidu.com/s/12XCilnFYyLFnSVoU_ShaSA 提取码&#xff1a;nfwc Oracle 21C 配置与登陆&#xff1a; 开始菜单 NetMa…

一文速览Llama 3及其微调:如何通过paper-review数据集微调Llama3 8B

前言 4.19日凌晨正准备睡觉时&#xff0c;突然审稿项目组的文弱同学说&#xff1a;Meta发布Llama 3系列大语言模型了 一查&#xff0c;还真是 本文以大模型开发者的视角&#xff0c;基于Meta官方博客的介绍&#xff1a;Introducing Meta Llama 3: The most capable openly a…

记录收集博客园美化代码

记录了一些好看实用的博客园美化主题🌃 初始微改版预览页面点击查看代码 /* 全局字体设定 */ #cnblogs_post_body {font-family: Roboto, sans-serif;color: #333; /* 增强字体颜色对比度,提高可读性 */ }/* 一级标题 */ #cnblogs_post_body h1 {font-size: 30px;font-weigh…

spring-boot学习记录

💭 记录spring-boot学习过程🕐 学习参考网站 1天搞定SpringBoot+Vue全栈开发-bilibili🕐 准备 🕑 项目热部署 视频中的idea版本较老,热部署实现参考IDEA2021 热部署-知乎 🕑 修改默认端口 在 src/main/resources/application.properties 文件中添加 server.port=80�…

Python学习从0开始——项目一day02数据库连接

Python学习从0开始——项目一day02数据库连接 一、在线云数据库二、测试数据库连接三、数据库驱动介绍四、SQL执行4.1插入测试数据4.2安装数据库连接模块4.3测试SQL语句执行4.4执行SQL的固定步骤及示例 一、在线云数据库 找了一个在线数据库&#xff0c;需要邮箱注册&#xff…

C语言结课实战项目_贪吃蛇小游戏

✨✨所属专栏&#xff1a;C语言✨✨ ✨✨作者主页&#xff1a;嶔某✨✨ 游戏源代码链接&#xff1a;function/贪吃蛇 钦某/c-language-learning - 码云 - 开源中国 (gitee.com) 最终实现效果&#xff1a; 实现基本的功能&#xff1a; void set_pos(short x, short y);//定位光…

需求 分析

需求分析的任务 需求分析的任务 1、需求分析是软件定义时期的最后一个阶段&#xff0c;它的基本任务是准确地回答“系统必须做什么?”这个问题。 2、确定系统必须完成哪些工作&#xff0c;也就是对目标系统提出完整、准确、清晰、具体的要求。 3、系统分析员应该写出软件需求…