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

【数据结构练习题】链表与LinkedList

news 来源：原创 2025/5/25 14:18:10

顺序表与链表LinkedList

选择题
链表面试题
- 1. 删除链表中等于给定值 val 的所有节点。
- 2. 反转一个单链表。
- 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
- 4. 输入一个链表，输出该链表中倒数第k个结点。
- 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
- 7. 链表的回文结构。
- 8. 输入两个链表，找出它们的第一个公共结点。
- 9. 给定一个链表，判断链表中是否有环。
- 10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL
- 11. 删除链表中重复的结点

选择题

1
在这里插入图片描述 A错误：头插不需要遍历链表，与链表长度无关
B错误：尾插不需要遍历链表，因为有一个引用指向了尾结点，可以直接插入
C错误：删除第一个节点也不需要遍历链表
D正确：删除最后一个节点之前，先要把倒数第二个节点找到，因为最后一个节点删除之后，需要将倒数第二个节点的next置为null 故需要遍历链表
因此选择D
2
在这里插入图片描述
答案：D
解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表
3

答案：D
解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。
4
在这里插入图片描述

5

A错误：ArrayList中的元素不一定有序，ArrayList没有要求里面的元素必须有序，可能有序也可能不有序
B正确：ArrayList中的元素可以通过下标修改
C错误：ArrayList中的元素没要求必须要唯一，可以唯一也可以重复
D错误：ArrayList中的元素是通过下标访问的，而不是通过key
故正确应该选B
6
在这里插入图片描述
A正确：ArrayList 和 LinkedList都是实现了List接口
B正确：ArrayList是动态类型顺序表，插入时当空间不足时会自动扩容
C正确：LinkedList底层是链表结构，链表不支持随机访问，如果要访问任意元素只能通过查找处理
D错误：LinkedList中插入或者删除元素，只需要修改几个引用的指向即可，不需要搬移愿意，时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移，时间复杂度O(N)

链表面试题

1. 删除链表中等于给定值 val 的所有节点。

OJ链接

class Solution {public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode cur=head.next;ListNode prev=head;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;}
}

2. 反转一个单链表。

OJ链接

class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;cur.next=head;head=cur;cur=curNext;}return head;}
}

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

OJ链接
在这里插入图片描述

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

4. 输入一个链表，输出该链表中倒数第k个结点。

OJ链接
在这里插入图片描述

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = Integer.parseInt(sc.next());ListNode head = new ListNode(-1);ListNode temp = head;//生成链表for (int i = 0; i < n; i++) {ListNode node = new ListNode(sc.nextInt());temp.next = node;temp = temp.next;}int k = Integer.parseInt(sc.next());//使用快慢指针if(getKthFromEnd(head.next,k) != null){System.out.println(getKthFromEnd(head.next,k).val);}else{System.out.println(0);}}}//通过快慢指针搜索public static ListNode getKthFromEnd(ListNode head,int k){if(k<=0||head==null){return null;}ListNode fast=head;ListNode slow=head;for(int i=0;i<k-1;i++){fast=fast.next;}while(fast.next!=null){fast=fast.next;slow=slow.next;}return slow;}
}
class ListNode{ListNode next;int val;ListNode(int val){this.val=val;next=null;}
}

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

OJ链接
在这里插入图片描述

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

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

OJ链接
在这里插入图片描述
有个易错不容易注意到：如果ae.next!=null链表会循环此时应该将ae.next=null

还要设想所有数都会大于x的可能，此时会bs==null 直接return as即可

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode bs=null;ListNode be=null;ListNode as=null;ListNode ae=null;ListNode cur=pHead;while(cur!=null){if(cur.val<x){//第一次插入if(bs==null){bs=be=cur;}else{be.next=cur;be=cur;//或be=be.next;}}else{if(as==null){as=ae=cur;}else{ae.next=cur;ae=cur;//或ae=ae.next;}}cur=cur.next;}//第一个段没有数据if(bs==null)return as;be.next=as;//防止最大的数据不是最后一个if(ae!=null)ae.next=null;return bs;}
}

7. 链表的回文结构。

OJ链接
在这里插入图片描述
若偶数时则循环到最后head.next==slow即可确定true

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereListNode slow=head;ListNode fast=head;//用快慢指针确定链表中点while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}ListNode cur=slow.next;//翻转后段链表while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}while(head!=slow){if(head.val!=slow.val)return false;if(head.next==slow) //偶数 head和slow不会相遇时return true;head=head.next;slow=slow.next;}return true;}
}

8. 输入两个链表，找出它们的第一个公共结点。

OJ链接
在这里插入图片描述

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//分别求2个链表的长度ListNode pL=headA;ListNode pS=headB;int lenA=0;int lenB=0;while(pL!=null){lenA++;pL=pL.next;}while(pS!=null){lenB++;pS=pS.next;}pL=headA;pS=headB;//保证pL指向最长的链表，pS指向最短的链表，len>0int len=lenA-lenB;if(len<0){pL=headB;pS=headA;len=lenB-lenA;}//2.让最长的链表先走差值步while(len!=0){pL=pL.next;len--;}//3.就是相遇的点while(pL!=pS){pL=pL.next;pS=pS.next;}return pL;}
}

9. 给定一个链表，判断链表中是否有环。

OJ链接

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head==null)return false;//可以不写ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow)return true;}return false;}
}

10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL

OJ链接

结论
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head==null)return null;ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow)break;}if(fast==null||fast.next==null)return null;fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}

11. 删除链表中重复的结点

OJ链接在这里插入图片描述
易忽略的点：应将手动将tmpHead.next置空防止后边到最后一个节点都是重复节点

import java.util.*;
/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead) {ListNode cur=pHead;ListNode newHead=new ListNode(-1);ListNode tmpHead=newHead;//遍历每一个节点while(cur!=null){if(cur.next!=null&&cur.val==cur.next.val){//一直让cur走到不重复的节点 while(cur.next!=null&&cur.val==cur.next.val){cur=cur.next;}                    cur=cur.next;}else{//把这个节点加入到不重复链表中tmpHead.next=cur;tmpHead=tmpHead.next;cur=cur.next;}}//手动将tmpHead.next置空防止后边到最后一个节点都是重复节点 tmpHead.next=null;return newHead.next;}
}

【数据结构练习题】链表与LinkedList

顺序表与链表LinkedList 选择题链表面试题1. 删除链表中等于给定值 val 的所有节点。2. 反转一个单链表。3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。4. 输入一个链表，输出该链…...

编程日记 2025/5/25 14:18:10

使用 acme.sh 申请域名 SSL/TLS 证书完整指南

使用 acme.sh 申请域名 SSL/TLS 证书完整指南简介为什么选择 acme.sh 和 ZeroSSL？前置要求安装过程步骤一：安装 acme.sh步骤二：配置 ZeroSSL 证书申请方法一：手动 DNS 验证（推荐新手使用）方法二&#xf…...

编程日记 2025/5/21 5:14:06

微信小程序开发入门

实现滚动需要设置高度和边框轮播图差值表达式（ {{表达式的值}} ）,info数据要写到js文件的data数据中小程序中常用的事件...

编程日记 2025/5/17 23:42:41

【LeetCode】9、回文数

【LeetCode】9、回文数文章目录一、数学: 除法和取模1.1 数学: 除法和取模二、多语言解法一、数学: 除法和取模 1.1 数学: 除法和取模例如 15251, offset 也是五位数的 10000 先判断首1和尾1, 再变为 525, offset 变为 100 再判断首5和尾5, 再变为 2, offset 变为 1 整个…...

编程日记 2025/5/20 8:15:15

面试题整理9----谈谈对k8s的理解2

面试题整理9----谈谈对k8s的理解2 1. Service 资源1.1 ServiceClusterIPNodePortLoadBalancerIngressExternalName 1.2 Endpoints1.3 Ingress1.4 EndpointSlice1.5 IngressClass 2. 配置和存储资源2.1 ConfigMap2.2 Secret2.3 PersistentVolume2.4 PersistentVolumeClaim2.5 St…...

编程日记 2025/5/24 7:19:00

fpga系列 HDL：Quartus II PLL (Phase-Locked Loop) IP核 (Quartus II 18.0)

在 Quartus II 中使用 PLL (Phase-Locked Loop) 模块来将输入时钟分频或倍频，并生成多个相位偏移或频率不同的时钟信号： 1. 生成 PLL 模块在 Quartus II 中： 打开 IP Components。 file:///C:/intelFPGA_lite/18.0/quartus/common/help/w…...

编程日记 2025/5/25 7:50:00

中国量子计算机领域的发展现状与展望

中国量子计算机领域的发展现状与展望摘要随着全球科技竞争的加剧，量子计算作为前沿技术领域备受瞩目。中国在量子计算机的研发方面取得了显著进展，本文将深入探讨中国量子计算机领域的现状、取得的成果、面临的挑战以及未来的发展方向，并…...

编程日记 2025/5/25 3:36:54

html（超文本标记语言）

声明！ 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下，如涉及侵权马上删除文章，笔记只是方便各位师傅的学习和探讨，文章所提到的网站以及内容，只做学习交流，其他均与本人以及泷羽sec团队无关&…...

编程日记 2025/5/25 14:11:27

如何在Windows系统上安装和配置Maven

Maven是一个强大的构建和项目管理工具，广泛应用于Java项目的自动化构建、依赖管理、项目构建生命周期控制等方面。在Windows系统上安装Maven并配置环境变量，是开发者开始使用Maven的第一步。本文将详细介绍如何在Windows系统上安装和配置Maven&#xff0…...

编程日记 2025/5/24 9:11:52

基于Python Scrapy的豆瓣Top250电影爬虫程序

Scrapy安装 Python实现一个简单的爬虫程序（爬取图片）_python简单扒图脚本-CSDN博客创建爬虫项目创建爬虫项目： scrapy startproject test_spider 创建爬虫程序文件： >cd test_spider\test_spider\spiders >scrapy g…...

编程日记 2025/5/25 14:15:01

mysql,数据库数据备份

mysql 一.数据库备份概念1.备份分类2.备份策略3.备份三要素二.完全备份操作1.物理备份(还原),冷备份2.逻辑备份,温备份三.percona软件的xtrabackup工具备份(2备份,3还原),增量,差异1.percona软件安装2.增量备份(还原)3.差异备份四.binlog日志1.binlog日志概念2.查看binlog日志信…...

编程日记 2025/5/19 13:56:43

模仿elementui的Table，实现思路

vue2子组件使用render，给子子组件插槽传值和elementui的Table一样使用render 在 Vue 2 中，子组件使用render函数向子子组件插槽传值可以通过以下步骤实现： 1、创建子组件首先创建一个子组件，在子组件中使用render函数来渲染内容…...

编程日记 2025/5/20 6:46:16

Android Studio AI助手---Gemini

从金丝雀频道下载最新版 Android Studio，以利用所有这些新功能，并继续阅读以了解新增内容。 Gemini 现在可以编写、重构和记录 Android 代码 Gemini 不仅仅是提供指导。它可以编辑您的代码，帮助您快速从原型转向实现，实现常见的…...

编程日记 2025/5/25 2:33:56

大模型+安全实践之春天何时到来？

引子：距《在大模型实践旅途中摸了下上帝的脚指头》一文发布近一年，2024年笔者继续全情投入在大模型＋安全上，深度参与了一些应用实践，包括安全大模型首次大规模应用在国家级攻防演习、部分项目的POC直到项目落地，也推动了一些场景安全大模型应用从0到3的孵化上市。这一年也…...

编程日记 2025/5/22 6:20:03

ACL技术---访问控制列表

是一种策略。对于网络中的流量而言，通常有两种处理方式允许拒绝 ACL 的原理配置了 ACL 的网络设备会根据事先设定好的报文匹配规则对经过该设备的报文进行匹配，然后对报文执行预先设定好的处理动作。 ACL 的功能访问控制：在设备…...

编程日记 2025/5/19 11:57:26

第25周：文献阅读

目录摘要 Abstract 文献阅读现有问题提出方法创新点方法论实验研究数据集数据预处理仿真实验评价指标实验结果分析总结摘要本篇论文提出了一种基于深度学习框架的风速预测方法——SSA-BiLSTM网络，旨在提高风速预测的精确性。研究使…...

编程日记 2025/5/22 0:21:58

BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）

Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出） 目录 Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）分类效果基本描述…...

编程日记 2025/5/19 17:38:07

docker数据卷

什么是数据卷？ 在容器中是无法通过vi命令对一个容器中的资源做修改的，这个时候就需要通过数据卷将文件中的内容映射到宿主机，在宿主机修改的文件会更新到容器中，并且容器被删除后不会把数据卷删除，数据卷中的数据会被持…...

编程日记 2025/5/22 21:42:33

Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务间的通讯-信号量【入门三】

继续上一篇任务创建【Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务创建【入门二】-CSDN博客】今天要实现再创建一个任务。【二值和互斥都进行测试】 ①、通过任务A发送一个信号量，另一个任务得到信号量后再发送helloworld。 ②、两个任务通过互斥信…...

编程日记 2025/5/23 23:12:07

使用C#绘制具有平滑阴影颜色的曼德布洛特集分形

示例使用复数类在 C# 中轻松绘制曼德布洛特集分形解释了如何通过迭代方程绘制曼德布洛特集：...

编程日记 2025/5/23 23:12:04

Unittest01|TestCase

一、入门 1、新建测试文件打开pycharm→左上角新建项目→选择项目路径→选择python解释器→创建→点击新建好的项目，右键新建python文件→测试文件（py文件）命名必须以test开头 2、创建测试用例定义测试类：导入unittest模块→…...

编程日记 2025/5/20 18:50:29

Django实现异步视图asyncio请求

随着现代Web应用程序对性能和响应速度的需求不断增加，开发者们越来越倾向于采用异步编程来提升应用的效率和用户体验。在传统的Web开发框架中，通常采用同步请求方式，这意味着每一个请求都需要等待前一个请求完成后才能继续处理。对于高并发的请求，可能会出现性能瓶颈。而Dj…...

编程日记 2025/5/21 14:37:15

Apache Samza开源的分布式流处理框架

Apache Samza 是一个开源的分布式流处理框架，用于处理实时数据流和分布式任务。它最初由 LinkedIn 开发，并在 2014 年捐赠给 Apache 软件基金会。Samza 的设计目标是为开发人员提供一个易用、可靠、高效的流处理工具。以下是其关键特点和架构的简介：核心特点简单的编程模…...

编程日记 2025/5/21 22:33:33

Linux实验报告5-shell脚本编程进阶

目录一：实验目的二：实验内容 1 编写脚本，实现将当前目录中所有子目录的名称输出到屏幕上。 2 首先以你的姓氏的拼音为开头在当前用户的主目录下新建3个文件和2个子目录，如zi1，zi2，zi3以及子目录zi.d和…...

编程日记 2025/5/24 10:18:57

YOLO系列正传（四）YOLOv3论文精解(下)——损失函数推导与其他优化项

系列文章 YOLO系列基础 YOLO系列基础合集——小白也看得懂的论文精解-CSDN博客 YOLO系列正传 YOLO系列正传（一）类别损失与MSE损失函数、交叉熵损失函数-CSDN博客 YOLO系列正传（二）YOLOv3论文精解(上)——从FPN到darknet-53-C…...

编程日记 2025/5/20 21:59:19

【漏洞复现】CVE-2023-37461 Arbitrary File Writing

漏洞信息 NVD - cve-2023-37461 Metersphere is an opensource testing framework. Files uploaded to Metersphere may define a belongType value with a relative path like ../../../../ which may cause metersphere to attempt to overwrite an existing file in the d…...

编程日记 2025/5/23 23:12:01

顺序表与链表LinkedList

选择题

链表面试题

1. 删除链表中等于给定值 val 的所有节点。

2. 反转一个单链表。

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

4. 输入一个链表，输出该链表中倒数第k个结点。

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

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

7. 链表的回文结构。

8. 输入两个链表，找出它们的第一个公共结点。

9. 给定一个链表，判断链表中是否有环。

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

11. 删除链表中重复的结点

相关文章：

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL