【数据结构】 单链表面试题讲解
文章目录
- 引言
- 反转单链表
- 题目描述
- 示例:
- 题解思路
- 代码实现:
- 移除链表元素
- 题目描述:
- 示例
- 思路解析:
- 链表的中间结点
- 题目描述:
- 示例:
- 思路解析
- 代码实现如下:
- 链表中倒数第k个结点
- 题目描述
- 示例
- 思路解析:
- 代码实现如下:
- 总结
引言
单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
反转单链表
题目描述
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围: 0≤n≤1000
要求:空间复杂度 O(1) ,时间复杂度 O(n) 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
示例:
题解思路
(1)定义两个指针: pser 和 sur ;sur 在前 pser 在后。
(2)sur用于遍历,pser用于交换位置,并插入到头节点前面
(3)将head里面的next置为null
(4)每一次插入顺序为将sur的位置付给pser,然后sur向前走一步,令pser里的next设为head;这时候pser为头节点,我们再将pser赋给head作为新的头节点。每循环一次头节点向前走一步
(5)循环上述过程,直至 sur 到达链表尾部
代码实现:
import java.util.*;/** public class ListNode {* int val;* ListNode next = null;* public ListNode(int val) {* this.val = val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @return ListNode类*/public ListNode ReverseList (ListNode head) {// write code hereif (head == null || head.next == null) {return head;}ListNode sur = head.next;ListNode pser = head;head.next = null;while (sur != null) {pser = sur;sur = sur.next;pser.next = head;head = pser;}return head;}
}
移除链表元素
题目描述:
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例
思路解析:
我们依旧需要对该单链表进行判断,如果为空,就直接返回
由于我们需要删除很多个这样的节点,但是我们的单链表却是单向的,按照上面的写法,我们则需要遍历很多次单链表,大大的增加了复杂度,我们为了降低时间复杂度,使它降为O(N);
我们设两个遍历节点,进行遍历,一个在前为cur,一个在后prev
前面的cur负责进行遍历删除,后面的prev负责跟在cur后面记录cur的上一节点
当cur下一节点不是我们所要删除的元素时,这时候我们将prev变为我们当前节点的cur,而cur变为当前节点的next
当前的删除方法只能删除第一个节点以后的元素,所以我们还需要处理第一个元素是我们所需要删除的情况。
代码实现如下
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null) {return null;}ListNode prev = head;ListNode cur = head.next;while (cur != null) {if(cur.val == val) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == val) {head = head.next;}return head;}
}
链表的中间结点
题目描述:
给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例:
思路解析
我们依旧两个定义两个指针,一个一次性走两步,一个一次性走一步
当快的指针到达终点时,慢的指针所☞指位置就是我们所需要的中间位置
就像大人与小孩子一起走路,大人的速度是小孩子的两倍
大人到达终点时,小孩子才走到一半!
代码实现如下:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;//1、找中间节点while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
}
注意:fast != null与fast.next != null不可以调换
链表中倒数第k个结点
题目描述
输入一个链表,输出该链表中倒数第k个结点。
示例
输入:
1,{1,2,3,4,5}
返回值:
{5}
思路解析:
依旧是两个指针,分别为fast和slow,fast先出发,fast出发k-1步后,slow出发,中间保持k-1个节点的距离,fast所指向下一节点为null时结束
代码实现如下:
import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head, int k) {if (k <= 0 || head == null) {return null;}ListNode fast = head;ListNode slow = head;//1. fast走k-1步while (k - 1 != 0) {fast = fast.next;if (fast == null) {return null;}k--;}//2、3、while (fast.next != null) {fast = fast.next;slow = slow.next;}return slow;}
}
总结
关于《【数据结构】 单链表面试题讲解》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!
相关文章:
【数据结构】 单链表面试题讲解
文章目录 引言反转单链表题目描述示例:题解思路代码实现: 移除链表元素题目描述:示例思路解析: 链表的中间结点题目描述:示例:思路解析代码实现如下: 链表中倒数第k个结点题目描述示例思路解析&…...
C++ string类的模拟实现
模拟实现string类不是为了造一个更好的轮子,而是更加理解string类,从而来掌握string类的使用 string类的接口设计繁多,故而不会全部涵盖到,但是核心的会模拟实现 库中string类是封装在std的命名空间中的,所以在模拟…...
Qt实现简单的漫游器
文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。 QOpenGLWidget 提供了三个便捷的虚函数,可以重载,用来重新实现典型的OpenGL任务: paintGL:渲染…...
【c语言】文件操作
朋友们,大家好,今天分享给大家的是文件操作的相关知识,跟着我一起学习吧!! 🎈什么是文件 磁盘上的文件是文件。 但是在程序设计中,我们一般谈的文件有两种:程序文件、数据文件 程序文…...
【Unity】坐标转换经纬度方法(应用篇)
【Unity】坐标转换经纬度方法(应用篇) 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法,理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法(原理篇),在实际使用中,…...
element时间选择器el-date-picter使用disabledDate指定禁用的日期
需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…...
出学校干了 5 年外包,已经废了
如果不是女朋友和我提分手,我估计现在还没醒悟 本科大专,17年通过校招进入某软件公司做测试,干了接近5年的功能。 今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经…...
day-23 代码随想录算法训练营(19)part09
669.修剪二叉搜索树 思路一:根据二叉搜索树的特性进行中间值与去区间值判断,有三种情况:1.在区间中,所以左右子树都可能在区间中; 2.在区间外面的左侧,必然只有右子树可能存在区间中;3.在区间外…...
JVM编译优化
即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...
vue浏览器插件安装-各种问题
方法1:vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址: Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源(推荐使用nrm,这一步是为…...
maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven
Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 Maven项目对象模型(POM),可以通过一小段描述信息来管理项目的构建,报告和文档的…...
Mac鼠标增强工具Smooze Pro
Smooze Pro是一款Mac上的鼠标手势增强工具,可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作,包括单指、双指、三指和四指手势,并且可以自定义每种手势的功能。例如,您可以使用单指向下滑动手势来启动Expos视…...
数据结构-单链表(C语言简单实现)
简介 以顺序结构进行数据存储时,它的特点就是可以用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的,这些数据可以存在内存未被占用的任意位置。它也是有缺点的,就是在插入和删除时需要移…...
.netcore grpc身份验证和授权
一、鉴权和授权(grpc专栏结束后会开启鉴权授权专栏欢迎大家关注) 权限认证这里使用IdentityServer4配合JWT进行认证通过AddAuthentication和AddAuthorization方法进行鉴权授权注入;通过UseAuthentication和UseAuthorization启用鉴权授权增加…...
分布式 - 服务器Nginx:一小时入门系列之负载均衡
文章目录 1. 负载均衡2. 负载均衡策略1. 轮询策略2. 最小连接策略3. IP 哈希策略4. 哈希策略5. 加权轮询策略 1. 负载均衡 跨多个应用程序实例的负载平衡是一种常用技术,用于优化资源利用率、最大化吞吐量、减少延迟和确保容错配置。使用 nginx 作为非常有效的HT…...
Linux学习之基本指令二
-----紧接上文 在了解cat指令之前,我们首先要了解到Linux下一切皆文件,在学习c语言时我们就已经了解到了 对文件输入以及读入的操作(向显示器打印,从键盘读取数据),对于Linux下文件的操作,也是…...
神经网络基础-神经网络补充概念-41-梯度的数值逼近
概念 梯度的数值逼近是一种用于验证梯度计算正确性的方法,它通过近似计算梯度来与解析计算的梯度进行比较。虽然数值逼近在实际训练中不常用,但它可以用来检查手动或自动求导的实现是否正确。 代码实现 import numpy as np# 定义函数 f(x) x^2 def f…...
tornado在模板中遍历二维数组
要在Tornado模板中遍历一个二维数组,你可以使用Tornado的模板语法来实现迭代和显示数组中的每个元素。 以下是一个示例,演示如何在Tornado模板中遍历和显示二维数组的内容: template.html: <!DOCTYPE html> <html> <head&g…...
前端-初始化Vue3+TypeScript
如果使用如下命令初始化项目,项目很干净,很适合了解项目的各个结构。 npm init vitelatest如果使用如下命令初始化项目,是可以选择你需要的组件 npm init vuelatest...
龙蜥社区安全联盟(OASA)正式成立,启明星辰、绿盟、360 等 23 家厂商重磅加入
7 月 28 日,由启明星辰、绿盟、360、阿里云、统信软件、浪潮信息、中兴通讯|中兴新支点、Intel、中科院软件所等 23 家单位共同发起的龙蜥社区安全联盟(OASA,OpenAnolisSecurityAlliance)(以下简称“安全联…...
Flask-SQLAlchemy
认识Flask-SQLAlchemy Flask-SQLAlchemy 是一个为 Flask 应用增加 SQLAlchemy 支持的扩展。它致力于简化在 Flask 中 SQLAlchemy 的使用。SQLAlchemy 是目前python中最强大的 ORM框架, 功能全面, 使用简单。 ORM优缺点 优点 有语法提示, 省去自己拼写SQL,保证SQL…...
大数据bug-sqoop(二:sqoop同步mysql数据到hive进行字段限制。)
一:sqoop脚本解析。 #!/bin/sh mysqlHost$1 mysqlUserName$2 mysqlUserPass$3 mysqlDbName$4 sql$5 split$6 target$7 hiveDbName$8 hiveTbName$9 partFieldName${10} inputDate${11}echo ${mysqlHost} echo ${mysqlUserName} echo ${mysqlUserPass} ec…...
Windows小记
一、域控制器升级的先决条件验证失败。 新建域时,本地 Administrator 帐户将成为域 Administrator 帐户。无法新建域,因为本地 Administrator 帐户密码不符合要求。 目前,本地 Administrator 帐户不需要密码。我们建议你使用网络用户命令行工…...
centos安装elasticsearch7.9
安装es 下载elasticsearch安装包解压安装包,并修改配置文件解压进入目录修改配置文件 添加用户,并修改所有者切换用户,运行es如何迁移旧版本的数据 下载elasticsearch安装包 下载地址如下,版本号可以替换成自己想要的。 这里需要注意一点&am…...
221、仿真-基于51单片机的智能啤酒发酵罐多点温度压力水位排水加水检测报警系统设计(程序+Proteus仿真+配套资料等)
毕设帮助、开题指导、技术解答(有偿)见文未 目录 一、硬件设计 二、设计功能 三、Proteus仿真图 编辑 四、程序源码 资料包括: 需要完整的资料可以点击下面的名片加下我,找我要资源压缩包的百度网盘下载地址及提取码。 方案选择 单片机的选择 方…...
C语言好题解析(三)
目录 选择题一选择题二选择题三选择题四编程题一编程题二 选择题一 以下程序段的输出结果是()#include<stdio.h> int main() { char s[] "\\123456\123456\t"; printf("%d\n", strlen(s)); return 0; }A: 12 B: 13 …...
OpenCV之remap的使用
OpenCV中使用remap实现图像的重映射。 重映射是指将图像中的某一像素值赋值到指定位置的操作:g(x,y) f ( h(x,y) ), 在这里, g( ) 是目标图像, f() 是源图像, 而h(x,y) 是作用于 (x,y) 的映射方法函数。为了完成映射过程, 需要获得一些插值为…...
leetcode 377. 组合总和 Ⅳ
2023.8.17 本题属于完全背包问题,乍一看和昨天那题 零钱兑换II 类似,但细看题目发现:今天这题是排列问题,而“零钱兑换II”是组合问题。排列问题强调顺序,而组合顺序不强调顺序。 这里先说个结论:先遍历物品…...
C++笔记之花括号和圆括号初始化区别,列表初始化和初始化列表区别
C笔记之花括号和圆括号初始化区别,列表初始化和初始化列表区别 code review! 文章目录 C笔记之花括号和圆括号初始化区别,列表初始化和初始化列表区别1.花括号{}进行初始化和圆括号()进行初始化2.列表初始化(list initialization࿰…...
git报错Add correct host key
想克隆备份的笔记库,失败。 测试连接github报错如下。 $ ssh -T gitgithub.comWARNING: POSSIBLE DNS SPOOFING DETECTED! The RSA host key for github.com has changed, and the key for the corresponding IP address 140.82.121.4 is unknown. This c…...
Kvm配置ovs网桥
环境:部署在kvm虚拟环境上(让虚拟机和宿主机都可以直接从路由器获取到独立ip) 1、安装ovs软件安装包并启动服务(一般采用源码安装,此处用yum安装) yum install openvswitch-2.9.0-3.el7.x86_64.rpm syste…...
AraNet:面向阿拉伯社交媒体的新深度学习工具包
阿拉伯语是互联网上第四大最常用的语言,它在社交媒体上的日益增加为大规模研究阿拉伯语在线社区提供了充足的资源。然而,目前很少有工具可以从这些数据中获得有价值的见解,用于决策、指导政策、协助应对等。这种情况即将改变吗? …...
P13-CNN学习1.3-ResNet(神之一手~)
论文地址:CVPR 2016 Open Access Repository https://arxiv.org/pdf/1512.03385.pdf Abstract 翻译 深层的神经网络越来越难以训练。我们提供了一个残差学习框架用来训练那些非常深的神经网络。我们重新定义了网络的学习方式,让网络可以直接学习输入信息与输出信息…...
【C++】set/multiset容器
1.set基本概念 #include <iostream> using namespace std;//set容器构造和赋值 #include<set>//遍历 void printSet(const set<int>& st) {for (set<int>::const_iterator it st.begin(); it ! st.end(); it){cout << *it << " …...
docker拉取镜像时报错Error response from daemon: Head ““no basic auth credentials
一:场景:新搭建一台服务器,需要拉取公司私有镜像仓库。 docker拉取私有仓库报如下错误: Error response from daemon: Head "" no basic auth credentials 二:解决方式 docker私有仓库需要登录授权,因此…...
Redis消息传递:发布订阅模式详解
目录 1.Redis发布订阅简介 2.发布/订阅使用 2.1 基于频道(Channel)的发布/订阅 2.2 基于模式(pattern)的发布/订阅 3.深入理解Redis的订阅发布机制 3.1 基于频道(Channel)的发布/订阅如何实现的? 3.2 基于模式(Pattern)的发布/订阅如何实现的? 3.3 Sp…...
最强自动化测试框架Playwright(36)- 句柄
剧作家可以为页面 DOM 元素或页面内的任何其他对象创建句柄。这些句柄存在于 Playwright 进程中,而实际对象位于浏览器中。有两种类型的句柄: JSHandle 引用页面中的任何 JavaScript 对象ElementHandle 引用页面中的 DOM 元素,它具有额外的方…...
推荐一个绘图平台(可替代Visio)
不废话,简易记网址: draw.io 网站会重定向到:https://app.diagrams.net/...
【探索Linux】—— 强大的命令行工具 P.6(调试器-gdb、项目自动化构建工具-make/Makefile)
阅读导航 前言一、什么是调试器二、详解 GDB - 调试器1.使用前提2.经常使用的命令3.使用小技巧 三、项目自动化构建工具 - make/Makefile1. make命令⭕语法⭕常用选项⭕常用操作⭕make命令的工作原理⭕make命令的优势: 2.Makefile文件⭕Makefile的基本结构⭕Makefil…...
echarts-convert.js使用
echarts-convert.js demo 点击下载 1、本地安装phantom.js插件 window版本下载 2、更改文件路径 (D:\phantomjs-2.1.1-windows\bin)改为本地项目文件路径 3、打开cmd命令行,并格式化语言 运行以下命令 将命令行语言改为中文简体 chcp…...
数据结构之队列详解(包含例题)
一、队列的概念 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操…...
Prometheus的搭建与使用
一、安装Prometheus 官网下载地址:Download | Prometheus 解压:tar -zxvf prometheus-2.19.2.linux-amd64.tar.gz重命名: mv prometheus-2.19.2.linux-amd64 /home/prometheus进入对应目录: cd /home/prometheus查看配置文件&am…...
实战指南,SpringBoot + Mybatis 如何对接多数据源
系列文章目录 MyBatis缓存原理 Mybatis plugin 的使用及原理 MyBatisSpringboot 启动到SQL执行全流程 数据库操作不再困难,MyBatis动态Sql标签解析 从零开始,手把手教你搭建Spring Boot后台工程并说明 Spring框架与SpringBoot的关联与区别 Spring监听器…...
论文阅读——Imperceptible Adversarial Attack via Invertible Neural Networks
Imperceptible Adversarial Attack via Invertible Neural Networks 作者:Zihan Chen, Ziyue Wang, Junjie Huang*, Wentao Zhao, Xiao Liu, Dejian Guan 解决的问题:虽然视觉不可感知性是对抗性示例的理想特性,但传统的对抗性攻击仍然会产…...
List和ObservableCollection和ListBinding在MVVM模式下的对比
List和ObservableCollection和ListBinding在MVVM模式下的对比 List 当对List进行增删操作后,并不会对View进行通知。 //Employee public class Employee : INotifyPropertyChanged {public event PropertyChangedEventHandler? PropertyChanged;public string N…...
insightface安装过程中提示 Microsoft Visual C++ 14.0 or greater is required.
pip install insightface安装过程中提示 Microsoft Visual C 14.0 or greater is required.Get it with "Microsoft C Build Tools": https://visualstudio.microsoft.com/visual-cpp-build-tools/ 根据提示网站访问官网下载生成工具 打开软件后会自动更新环境&#…...
mongodb数据库
目录 一、数据库 二、文档 三、集合 四、元数据 五、MongoDB 数据类型 1、ObjectId 2、字符串 3、时间戳 4、日期 一、数据库 一个 mongodb 中可以建立多个数据库。 MongoDB 的默认数据库为"db",该数据库存储在 data 目录中。 MongoDB 的单…...
OpenCV-Python中的图像处理-图像特征
OpenCV-Python中的图像处理-图像特征 图像特征Harris角点检测亚像素级精度的角点检测Shi-Tomasi角点检测SIFT(Scale-Invariant Feature Transfrom)SURF(Speeded-Up Robust Features)FAST算法BRIEF(Binary Robust Independent Elementary Features)算法ORB (Oriented FAST and R…...
Ajax入门+aixos+HTTP协议
一.Ajax入门 概念:AJAX是浏览器与服务器进行数据通信的技术 axios使用: 引入axios.js使用axios函数:传入配置对象,再用.then回调函数接受结果,并做后续处理 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>01.axios使用…...
conda创建虚拟环境
创建虚拟环境是在计算机上设置一个独立的空间,用于安装和运行特定版本的软件和依赖项,以避免与系统其他部分的冲突。 创建虚拟环境: conda create --name myenv python3.8 这将创建一个名为myenv的虚拟环境,并安装Python 3.8版本。…...