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

【数据结构】 单链表面试题讲解

文章目录

  • 引言
  • 反转单链表
    • 题目描述
    • 示例:
    • 题解思路
    • 代码实现:
  • 移除链表元素
    • 题目描述:
    • 示例
    • 思路解析:
  • 链表的中间结点
    • 题目描述:
    • 示例:
    • 思路解析
    • 代码实现如下:
  • 链表中倒数第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;}
}

总结

关于《【数据结构】 单链表面试题讲解》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

相关文章:

【数据结构】 单链表面试题讲解

文章目录 引言反转单链表题目描述示例&#xff1a;题解思路代码实现&#xff1a; 移除链表元素题目描述&#xff1a;示例思路解析&#xff1a; 链表的中间结点题目描述&#xff1a;示例&#xff1a;思路解析代码实现如下&#xff1a; 链表中倒数第k个结点题目描述示例思路解析&…...

C++ string类的模拟实现

模拟实现string类不是为了造一个更好的轮子&#xff0c;而是更加理解string类&#xff0c;从而来掌握string类的使用 string类的接口设计繁多&#xff0c;故而不会全部涵盖到&#xff0c;但是核心的会模拟实现 库中string类是封装在std的命名空间中的&#xff0c;所以在模拟…...

Qt实现简单的漫游器

文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。  QOpenGLWidget 提供了三个便捷的虚函数&#xff0c;可以重载&#xff0c;用来重新实现典型的OpenGL任务&#xff1a; paintGL&#xff1a;渲染…...

【c语言】文件操作

朋友们&#xff0c;大家好&#xff0c;今天分享给大家的是文件操作的相关知识&#xff0c;跟着我一起学习吧&#xff01;&#xff01; &#x1f388;什么是文件 磁盘上的文件是文件。 但是在程序设计中&#xff0c;我们一般谈的文件有两种&#xff1a;程序文件、数据文件 程序文…...

【Unity】坐标转换经纬度方法(应用篇)

【Unity】坐标转换经纬度方法&#xff08;应用篇&#xff09; 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法&#xff0c;理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法&#xff08;原理篇),在实际使用中&#xff0c…...

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 年外包,已经废了

如果不是女朋友和我提分手&#xff0c;我估计现在还没醒悟 本科大专&#xff0c;17年通过校招进入某软件公司做测试&#xff0c;干了接近5年的功能。 今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经…...

day-23 代码随想录算法训练营(19)part09

669.修剪二叉搜索树 思路一&#xff1a;根据二叉搜索树的特性进行中间值与去区间值判断&#xff0c;有三种情况&#xff1a;1.在区间中&#xff0c;所以左右子树都可能在区间中&#xff1b; 2.在区间外面的左侧&#xff0c;必然只有右子树可能存在区间中&#xff1b;3.在区间外…...

JVM编译优化

即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...

vue浏览器插件安装-各种问题

方法1&#xff1a;vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址&#xff1a; Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源&#xff08;推荐使用nrm&#xff0c;这一步是为…...

maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven

Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 ​ Maven项目对象模型(POM)&#xff0c;可以通过一小段描述信息来管理项目的构建&#xff0c;报告和文档的…...

Mac鼠标增强工具Smooze Pro

Smooze Pro是一款Mac上的鼠标手势增强工具&#xff0c;可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作&#xff0c;包括单指、双指、三指和四指手势&#xff0c;并且可以自定义每种手势的功能。例如&#xff0c;您可以使用单指向下滑动手势来启动Expos视…...

数据结构-单链表(C语言简单实现)

简介 以顺序结构进行数据存储时&#xff0c;它的特点就是可以用一组任意的存储单元存储数据元素&#xff0c;这组存储单元可以是连续的&#xff0c;也可以是不连续的&#xff0c;这些数据可以存在内存未被占用的任意位置。它也是有缺点的&#xff0c;就是在插入和删除时需要移…...

.netcore grpc身份验证和授权

一、鉴权和授权&#xff08;grpc专栏结束后会开启鉴权授权专栏欢迎大家关注&#xff09; 权限认证这里使用IdentityServer4配合JWT进行认证通过AddAuthentication和AddAuthorization方法进行鉴权授权注入&#xff1b;通过UseAuthentication和UseAuthorization启用鉴权授权增加…...

分布式 - 服务器Nginx:一小时入门系列之负载均衡

文章目录 1. 负载均衡2. 负载均衡策略1. 轮询策略2. 最小连接策略3. IP 哈希策略4. 哈希策略5. 加权轮询策略 1. 负载均衡 跨多个应用程序实例的负载平衡是一种常用技术&#xff0c;用于优化资源利用率、最大化吞吐量、减少延迟和确保容错配置。‎使用 nginx 作为非常有效的HT…...

Linux学习之基本指令二

-----紧接上文 在了解cat指令之前&#xff0c;我们首先要了解到Linux下一切皆文件&#xff0c;在学习c语言时我们就已经了解到了 对文件输入以及读入的操作&#xff08;向显示器打印&#xff0c;从键盘读取数据&#xff09;&#xff0c;对于Linux下文件的操作&#xff0c;也是…...

神经网络基础-神经网络补充概念-41-梯度的数值逼近

概念 梯度的数值逼近是一种用于验证梯度计算正确性的方法&#xff0c;它通过近似计算梯度来与解析计算的梯度进行比较。虽然数值逼近在实际训练中不常用&#xff0c;但它可以用来检查手动或自动求导的实现是否正确。 代码实现 import numpy as np# 定义函数 f(x) x^2 def f…...

tornado在模板中遍历二维数组

要在Tornado模板中遍历一个二维数组&#xff0c;你可以使用Tornado的模板语法来实现迭代和显示数组中的每个元素。 以下是一个示例&#xff0c;演示如何在Tornado模板中遍历和显示二维数组的内容&#xff1a; template.html: <!DOCTYPE html> <html> <head&g…...

前端-初始化Vue3+TypeScript

如果使用如下命令初始化项目&#xff0c;项目很干净&#xff0c;很适合了解项目的各个结构。 npm init vitelatest如果使用如下命令初始化项目&#xff0c;是可以选择你需要的组件 npm init vuelatest...

龙蜥社区安全联盟(OASA)正式成立,启明星辰、绿盟、360 等 23 家厂商重磅加入

7 月 28 日&#xff0c;由启明星辰、绿盟、360、阿里云、统信软件、浪潮信息、中兴通讯&#xff5c;中兴新支点、Intel、中科院软件所等 23 家单位共同发起的龙蜥社区安全联盟&#xff08;OASA&#xff0c;OpenAnolisSecurityAlliance&#xff09;&#xff08;以下简称“安全联…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...