LeetCode算法（链表）

今天的算法是链表篇，这篇比较简单，总体是之前完成的手写链表，几乎就是链表的大部分知识了，所以今天算是一个复习内容了。

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

所以第一步要设计一个节点类，如下：

public class Node<E> {//节点内的数据E data;//节点指向的下一个对象Node<E> next;public Node(E data, Node<E> next) {this.data = data;this.next = next;}
}

下面我们开始手写单向链表。

1.尾部添加

链接：设计链表

首先构建一个自己的链表，属性为    链表的长度，链表的头节点

对于尾部添加需要注意的是，需要知道链表的尾部节点是什么，所以第一步应该写一个方法，遍历链表找到尾节点。我们只需要判断每个节点的下一个指针是否为空，空的就是尾部节点。如下

    private Node<E> findEnd() {Node<E> node = first;while (node.next != null){node = node.next;}return node;}

然后就是尾部添加方法的实现。

思路：

（1）判断链表是否为空，如果为空，则该节点为头节点

（2）调用查询尾部节点的方法，拿到尾部节点

（3）尾部添加，长度加一

代码如下：

    public void add(E data) {Node<E> node = new Node<>(data, null);//首先判断头节点是否为空，如果为空则证明为空链表，第一次添加的节点为头节点if (first == null) {first = node;size++;return;}//找到链表的尾部Node<E> endNode = findEnd();endNode.next = node;size++;}

2.删除节点

链接：设计链表

删除节点有两种方式，一种是根据索引进行删除，另一种是根据节点内的数据进行删除

索引删除：

无论是删除还是添加，我们都需要注意，要考虑到头节点的情况，并对其做出相应的处理

首先需要一个方法，根据索引返回对应的节点，该方法不需要考虑头节点，因为我们需要在真正执行删除的方法中添加对应的逻辑就好，该方法为通用方法

举例：需要找到索引值为2的节点，那么在不考虑头节点的情况下，只需要找到1索引值的节点，就可以根据其next的指针，找到索引值为2的节点

node（2） = node（1）.next     所以只需要传入1，就可以了

代码如下：

    //寻找对于索引处的节点public Node<E> findNode(int index) {Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}

下面开始删除节点的方法。

思路：

（1）如果索引为0，也就是头节点，首先获取头节点的下一个节点，将当前头节点的数据和节点指针置空，最后将链表的头节点属性改为下一个节点，size减1

（2）如果索引不为0，首先调用寻找节点的方法，获取到该节点的上一个节点，这样就可以拿到三个节点的信息

上一个节点（a）    当前节点（b）    下一个节点（c）

1.  将a的节点指针，指向c

2.  将b的数据和节点指针置空

3.   size减1

代码如下：

//删除对应元素public void remove(int index) {//一：遍历链表找到对应节点和上一节点  (头节点的判断)//二：将上一节点的指向改为删除节点的指向//三：将连接的属性设置为null，size减1if (first != null && index == 0) {//1.获取头节点的下一节点，将头节点的属性清空//2.头节点重新赋值Node<E> next = first.next;first.next = null;first.data = null;first = next;} else {//上一个节点Node<E> prevNode = findNode(index - 1);//当前节点Node<E> node = prevNode.next;prevNode.next = node.next;node.next = null;node.data = null;}size--;}

节点数据删除：

对于节点数据删除来说，不能只删除一个节点，因为数据不是唯一的，可能多个节点的数据是相同的，这是一个注意的点，还有就是要考虑头节点删除的情况

思路：

（1）判断是否为头节点，如果删除的数据与头节点的数据相同的话，进行对应的逻辑：与索引删除的逻辑一样，只不过更改了判断条件

（2）不为头节点时，需要遍历整个链表，找到与删除数据一样的节点，并进行删除逻辑：

1. 依旧需要从头节点开始遍历，因为头节点已经判断过了，所以去判断头节点的下一个节点，也就是node.next

2. 如果是其数据为删除的数据，那么找到该节点的下一个节点（node.next.next），并将该节点置空（node.next），然后头节点更新节点指针，指向node.next.next，size减1

3.如果不为删除的数据，更新node节点，node=node.next；

代码如下：

    public void removeValue(E data) {// 删除头节点的情况while (first != null && data.equals(first.data)) {Node<E> nextNode = first.next;first.next = null;first.data = null;first = nextNode;size--;}// 删除其他节点的情况Node<E> node = first;while (node != null && node.next != null) {if (data.equals(node.next.data)) {//当前节点的下一个节点的下一个节点Node<E> nextNode = node.next.next;node.next.data = null; // 释放节点数据node.next.next = null; // 释放节点指针node.next = nextNode; // 更新指向size--;}else {node = node.next;}}}

3.链表反转

链接：反转链表

这里需要理解的就是双指针的概念了，定义两个指针，a指针在b指针前，两个指针分别记录了相邻的节点，可以通过一个中间值temp，来更改两个节点的指向

下一个概念就是虚拟头，可以在头节点前想象一个空节点，data为null，next为头节点，在开始时，让a指针指向这个虚拟头，b指针指向头节点。

比如有 1 -> 2 -> 3，反转需要做的是 1 <- 2 <- 3

第一步：将2的next更改为1。   第二步：将3的next更改为2

指针的移动为：a指向1 ，b指向2  --->   a指向2，b指向3

换成节点为：node=first 

nextNode = first.next 

node.next = preNode上一个节点信息，初始为null

到这里反转完成了，下面需要移动指针

上一个指针指向就变成了当前节点

下一个指针就变成了当前节点的下一个节点

代码如下：

    //链表反转public void reversal() {//定义，上一个节点，当前节点，下一个节点//从头节点开始Node<E> prevNode = null;Node<E> node = first;Node<E> nextNode = null;//遍历整个链表到尾部while (node != null){nextNode = node.next;node.next = prevNode;prevNode = node;node = nextNode;}first = prevNode;//当遍历到尾节点的时候，已经为空节点了，获取其上一个节点}

4.相交链表

链接：相交链表

简单来说，就是求两个链表交点节点的指针。 

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，这里不用纠结让A移动还是B移动，最终的结果两个链表的长度是一样的

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

代码如下：

    //链表相交public Node<E> IntersectingLinkedList(Node<E> headA, Node<E> headB) {Node<E> curA = headA;Node<E> curB = headB;int lenA = 0;int lenB = 0;//计算两个链表的长度while (curA != null) {lenA++;curA = curA.next;}while (curB != null) {lenB++;curB = curB.next;}//计算差值int gap = lenA - lenB;if (gap > 0){//证明A为长链表for (int i = 0; i < gap; i++) {headA = headA.next;}}else {//证明B为长链表gap = lenB - lenA;for (int i = 0; i < gap; i++) {headB = headB.next;}}//无论A还是B链表，两个链表的长度是一样的，所以直接判断即可while (headA != null) {if (headA != headB){headA = headA.next;headB = headB.next;}//相等，返回else {return headA;}}return null;}

测试：

public class TestMyLink {public static void main(String[] args) {// 创建链表MyLink<Integer> myLink = new MyLink<>();// 添加元素myLink.add(1);myLink.add(2);myLink.add(3);myLink.add(4);myLink.add(5);System.out.println("链表初始化后的元素：");System.out.println(myLink.printList());// 获取元素System.out.println("索引2处的元素：" + myLink.get(2)); // 应输出 3// 更新元素myLink.update(2, 10);System.out.println("更新索引2处的元素后的链表：");System.out.println(myLink.printList());// 在指定位置插入元素myLink.add(2, 7);System.out.println("在索引2处插入7后的链表：");System.out.println(myLink.printList());// 删除元素myLink.remove(0);System.out.println("删除索引0处的元素后的链表：");System.out.println(myLink.printList());// 头插法myLink.headAdd(0);System.out.println("头插法插入0后的链表：");System.out.println(myLink.printList());// 链表反转myLink.reversal();System.out.println("链表反转后的元素：");System.out.println(myLink.printList());// 删除元素2myLink.removeValue(2);// 打印链表System.out.println("删除元素2后的链表内容:");System.out.println(myLink.printList()); // 应该输出: "1 3 4"System.out.println(4/2);}}

结果：

成功！还有一些我就不详细去说了，思路都是一样的，大家可以看我之前的手写单向链表，这篇更多也是复习，我自己再写一遍了，今天就到这里了！

完整代码：


public class MyLink<E> {//单向链表：链表的长度，节点，头节点private int size;//头节点Node<E> first;//尾插法，新增元素public void add(E data) {Node<E> node = new Node<>(data, null);//首先判断头节点是否为空，如果为空则证明为空链表，第一次添加的节点为头节点if (first == null) {first = node;size++;return;}//找到链表的尾部Node<E> endNode = findEnd();endNode.next = node;size++;}//寻找链表的尾部节点，节点内的指向下一个节点的属性为null，则为尾部节点private Node<E> findEnd() {//从头节点开始遍历Node<E> node = first;while (node.next != null) {node = node.next;}return node;}//删除对应元素public void remove(int index) {//一：遍历链表找到对应节点和上一节点  (头节点的判断)//二：将上一节点的指向改为删除节点的指向//三：将连接的属性设置为null，size减1if (index == 0) {//1.获取头节点的下一节点，将头节点的属性清空//2.头节点重新赋值Node<E> next = first.next;first.next = null;first.data = null;first = next;} else {Node<E> prevNode = findNode(index - 1);Node<E> node = prevNode.next;prevNode.next = node.next;node.data = null;node.next = null;}size--;}public void removeValue(E data) {// 删除头节点的情况while (first != null && data.equals(first.data)) {Node<E> nextNode = first.next;first.next = null;first.data = null;first = nextNode;size--;}// 删除其他节点的情况Node<E> node = first;while (node != null && node.next != null) {if (data.equals(node.next.data)) {// 删除节点Node<E> nextNode = node.next.next;node.next.data = null; // 释放节点数据node.next.next = null; // 释放节点指针node.next = nextNode; // 更新指向size--;} else {node = node.next;}}}//寻找对于索引处的节点public Node<E> findNode(int index) {Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}//获取对应索引处的数据public E get(int index) {Node<E> node = findNode(index);return node.data;}//修改对应索引处的数据public void update(int index, E data) {Node<E> node = findNode(index);node.data = data;}//向指定位置添加一个元素public void add(int index, E data) {// 检查索引是否有效if (index < 0 || index > size) {System.out.println("索引越界");return;}Node<E> node = new Node<>(data, null);if (index == 0) {// 头插法headAdd(data);} else if (index == size) {// 尾插法add(data); // 使用已有的尾插法} else {// 插入到指定位置Node<E> prevNode = findNode(index - 1);Node<E> nextNode = prevNode.next;prevNode.next = node;node.next = nextNode;size++;}}//头插法public void headAdd(E data) {//获取头节点，新节点指向头节点，并修改头节点变量Node<E> node = new Node<>(data, null);node.next = first;first = node;size++;}//链表反转public void reversal() {//定义，上一个节点，当前节点，下一个节点//从头节点开始Node<E> prevNode = null;Node<E> node = first;Node<E> nextNode = null;//遍历到链表的尾部while (node != null) {//保存当前节点的指向nextNode = node.next;//开始反转node.next = prevNode;//指向上一节点prevNode = node;//将当前节点变为上一个节点node = nextNode;//移动节点}first = prevNode;//当遍历到尾节点的时候，已经为空节点了}public String printList() {Node<E> node = first;StringBuilder list = new StringBuilder();while (node != null) {list.append(node.data);list.append(" ");node = node.next;}return list.toString();}//链表相交public Node<E> IntersectingLinkedList(Node<E> headA, Node<E> headB) {Node<E> curA = headA;Node<E> curB = headB;int lenA = 0;int lenB = 0;//计算两个链表的长度while (curA != null) {lenA++;curA = curA.next;}while (curB != null) {lenB++;curB = curB.next;}//计算差值int gap = lenA - lenB;if (gap > 0){//证明A为长链表for (int i = 0; i < gap; i++) {headA = headA.next;}}else {//证明B为长链表gap = lenB - lenA;for (int i = 0; i < gap; i++) {headB = headB.next;}}//无论A还是B链表，两个链表的长度是一样的，所以直接判断即可while (headA != null) {if (headA != headB){headA = headA.next;headB = headB.next;}//相等，返回else {return headA;}}return null;}}

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

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

相关文章

Docker：容器化和虚拟化

Docker：容器化和虚拟化

虚拟化 虚拟化是一种资源管理技术&#xff0c;它将计算机的各种实体资源&#xff08;如CPU、内存、磁盘空间、网络适配器等&#xff09;予以抽象、转换后呈现出来&#xff0c;并可供分割、组合为一个或多个电脑配置环境。这些资源的新虚拟部分是不受现有资源的架设方式、地域或…
阅读更多...
如何有效提升MySQL大表分页查询效率（本文以一张900万条数据体量的表为例进行详细解读）

如何有效提升MySQL大表分页查询效率（本文以一张900万条数据体量的表为例进行详细解读）

文章目录 1、提出问题1.1 问题测试 2、解决问题&#xff08;三种方案&#xff09;2.1、方案一&#xff1a;查询的时候&#xff0c;只返回主键 ID2.2、方案二&#xff1a;查询的时候&#xff0c;通过主键 ID 过滤2.3、方案三&#xff1a;采用 elasticSearch 作为搜索引擎 3、总结…
阅读更多...
DGUS屏使用方法

DGUS屏使用方法

1、DGUS工程下载 迪文DGUS屏的所有硬件参数和资料下载&#xff0c;都是通过屏上的SD/SDHC接口来完成的&#xff0c;文件必须使用FAT32文件格式。第一次使用SD卡前&#xff0c;推荐先格式化一次&#xff0c;流程如下&#xff1a; 1、 右键单击SD卡&#xff0c;在弹出来的菜单中选…
阅读更多...
设计产品宣传册没头绪？推荐一个超多产品宣传册、画册的案例网站

设计产品宣传册没头绪？推荐一个超多产品宣传册、画册的案例网站

在当今市场竞争激烈的背景下&#xff0c;产品宣传册和画册是企业宣传的重要手段之一。一本独具匠心的宣传册&#xff0c;不仅能够准确传达产品特点&#xff0c;还能吸引潜在客户&#xff0c;提升品牌形象。然而&#xff0c;设计一本优秀的宣传册并非易事&#xff0c;许多设计师…
阅读更多...
接口测试（八）jmeter——参数化（CSV Data Set Config）

接口测试（八）jmeter——参数化（CSV Data Set Config）

一、CSV Data Set Config 需求&#xff1a;批量注册5个用户&#xff0c;从CSV文件导入用户数据 1. 【线程组】–>【添加】–>【配置元件】–>【CSV Data Set Config】 2. 【CSV数据文件设置】设置如下 3. 设置线程数为5 4. 运行后查看响应结果
阅读更多...
【网页布局技术】项目五 使用CSS设置导航栏

【网页布局技术】项目五 使用CSS设置导航栏

《CSSDIV网页样式与布局案例教程》 徐琴 目录 任务一 制作简单纵向导航栏支撑知识点1&#xff0e;合理利用display:block属性2&#xff0e;利用margin-bottom设置间隔效果3&#xff0e;利用border设置特殊边框 任务二 制作简单横向导航栏任务三 制作带图片效果的横向导航栏任务…
阅读更多...
基于LangChain构建安全Agent应用实践（含代码）

基于LangChain构建安全Agent应用实践（含代码）

概述&#xff1a;本文基于langchain和Cyber Security Breaches数据集构建Agent&#xff0c;并基于该Agent实现了数据分析、趋势图输出、预测攻击态势三个功能&#xff0c;最后给出Agent在安全领域应用的三点启示。 前提&#xff1a; 1、拥有openai API KEY&#xff1b;&#…
阅读更多...
机器学习-决策树

机器学习-决策树

登录后复制 import numpy as np import matplotlib.pyplot as plt from sklearn import datasetsiris datasets.load_iris() X iris.data[:,2:] y iris.target plt.scatter(X[y0,0], X[y0,1]) plt.scatter(X[y1,0], X[y1,1]) plt.scatter(X[y2,0], X[y2,1]) plt.show() 1.2.…
阅读更多...
为什么大模型都是Decoder-only结构？

为什么大模型都是Decoder-only结构？

扫一扫下方&#xff0c;获取更多面试真题的集合 在探讨当前大型语言模型&#xff08;LLM&#xff09;普遍采用Decoder-only架构的现象时&#xff0c;我们可以从以下几个学术角度进行分析&#xff1a; 注意力机制的满秩特性&#xff1a;Decoder-only架构采用的因果注意力机制&am…
阅读更多...
Linux系统块存储子系统分析记录

Linux系统块存储子系统分析记录

1 Linux存储栈 通过网址Linux Storage Stack Diagram - Thomas-Krenn-Wiki-en&#xff0c;可以获取多个linux内核版本下的存储栈概略图&#xff0c;下面是kernel-4.0的存储栈概略图&#xff1a; 2 存储接口、传输速度 和 协议 2.1 硬盘 《深入浅出SSD&#xff1a;固态存储核心…
阅读更多...
北京迅为iTOP-LS2K0500开发板快速使用编译环境虚拟机Ubuntu基础操作及设置

北京迅为iTOP-LS2K0500开发板快速使用编译环境虚拟机Ubuntu基础操作及设置

迅为iTOP-LS2K0500开发板 迅为iTOP-LS2K0500开发板采用龙芯LS2K0500处理器&#xff0c;基于龙芯自主指令系统&#xff08;LoongArch&#xff09;架构&#xff0c;片内集成64位LA264处理器核、32位DDR3控制器、2D GPU、DVO显示接口、两路PClE2.0、两路SATA2.0、四路USB2.0、一路…
阅读更多...
电子电气架构 --- 车载芯片现状

电子电气架构 --- 车载芯片现状

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 所有人的看法和评价都是暂时的&#xff0c;只有自己的经历是伴随一生的&#xff0c;几乎所有的担忧和畏惧…
阅读更多...
MySQL分层结构由哪些组成？

MySQL分层结构由哪些组成？

1、MySQL分层结构由哪些组成&#xff1f; MySQL按照功能模块可以分为3层&#xff1a;连接层、服务层和存储引擎层。 连接层位于Server服务层的最外层&#xff0c;负责与客户端的直接交互&#xff0c;从功能上单独划分一层更合适。 不同的存储引擎在存储层有不同的实现&#x…
阅读更多...
Vue3入门--[vue/compiler-sfc] Unexpected token, expected “,“ (18:0)

Vue3入门--[vue/compiler-sfc] Unexpected token, expected “,“ (18:0)

新手小白学习Vue–入门就踩坑系列 问题描述 创建了一个Person.vue&#xff0c;保存后直接报错&#xff1a; [plugin:vite:vue] [vue/compiler-sfc] Unexpected token, expected "," (18:0) 在网上搜了半天也没找到原因&#xff0c;最后还得靠自己&#xff0c;现将解…
阅读更多...
【宠粉赠书】大模型项目实战：多领域智能应用开发

【宠粉赠书】大模型项目实战：多领域智能应用开发

在当今的人工智能与自然语言处理领域&#xff0c;大型语言模型&#xff08;LLM&#xff09;凭借其强大的生成与理解能力&#xff0c;正在广泛应用于多个实际场景中。《大模型项目实战&#xff1a;多领域智能应用开发》为大家提供了全面的应用技巧和案例&#xff0c;帮助开发者深…
阅读更多...
java：入门基础（1）

java：入门基础（1）

练习一&#xff1a;文字版格斗游戏 需求: ​ 格斗游戏&#xff0c;每个游戏角色的姓名&#xff0c;血量&#xff0c;都不相同&#xff0c;在选定人物的时候&#xff08;new对象的时候&#xff09;&#xff0c;这些信息就应该被确定下来。 举例&#xff1a; ​ 程序运行之后…
阅读更多...
Apache Paimon介绍

Apache Paimon介绍

目录 背景 诞生 应用场景 实时数据分析与查询 流批一体处理 低成本高效存储 具体业务场景示例 总结 系统架构 存储层 元数据管理 计算层 数据摄入和输出 查询优化 扩展性和可靠性 生态系统集成 总结 核心概念 表&#xff08;Table&#xff09; 模式&#xf…
阅读更多...
书生实战营第四期-第三关 Git+InternStudio

书生实战营第四期-第三关 Git+InternStudio

一、任务1: 破冰活动&#xff1a;自我介绍 1.fork项目到自己的账号下 2. 配置git并克隆项目到InternStudio本地 3.创建分支 4.创建自己的介绍文件 5.提交更改分支 6.推送分支到远程仓库 这里推送时会报错 问题解决&#xff1a;将密码换成access token 7.检查提交内容 分支…
阅读更多...
【商汤科技-注册/登录安全分析报告】

【商汤科技-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…
阅读更多...
2-134 基于matlab的图像边缘检测

2-134 基于matlab的图像边缘检测

基于matlab的图像边缘检测&#xff0c;采用六种算子(分别是gabor、拉普拉斯、priwitt、robert、sobel、wallis微分算子&#xff09;&#xff0c;对图象进行边缘检测比较&#xff0c;输出边缘检测结果。可对比效果优劣。程序已调通&#xff0c;可直接运行。 下载源程序请点链接…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023