数据结构-链表笔记

移除节点

203. 移除链表元素 - 力扣（LeetCode）

/*** 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) {// 创建一个虚拟头节点，方便处理删除头节点的情况ListNode dummyHead = new ListNode();dummyHead.next = head;// 初始化双指针ListNode pre = dummyHead; // pre指向当前节点的前一个节点ListNode cur = head;      // cur指向当前节点// 遍历链表while (cur != null) {// 如果当前节点的值等于要删除的值if (cur.val == val) {// 跳过当前节点，直接链接前一个节点到当前节点的下一个节点pre.next = cur.next;} else {// 如果当前节点的值不等于要删除的值，更新 pre 指针为当前节点pre = cur;}// 无论当前节点的值是否被删除，都移动 cur 指针到下一个节点cur = cur.next;}// 返回新的头节点，跳过虚拟头节点return dummyHead.next;}
}

设计链表

在链表类中实现这些功能：得到第 index 个节点的值，

在链表的第一个元素之前添加一个值为 val 的节点，

将值为 val 的节点追加到链表的最后一个元素，

在链表中的第 index 个节点之前添加值为 val  的节点，

删除链表中的第 index 个节点

707. 设计链表 - 力扣（LeetCode）

解法:单链表

class ListNode {int val; // 节点的值ListNode next; // 指向下一个节点的指针ListNode() {} // 默认构造函数ListNode(int val) { // 带值的构造函数this.val = val;}
}class MyLinkedList {// size 存储链表元素的个数int size;// 虚拟头结点，便于处理头节点的插入和删除ListNode dummyHead;public MyLinkedList() {size = 0; // 初始化链表大小为 0dummyHead = new ListNode(0); // 创建虚拟头结点}// 获取链表中第 index 个节点的值，索引从 0 开始public int get(int index) {// 检查索引是否有效if (index < 0 || index >= size) {return -1; // 返回 -1 表示索引无效}ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的节点for (int i = 0; i <= index; i++) {curNode = curNode.next; // 移动到下一个节点}return curNode.val; // 返回目标节点的值}// 在链表头部添加一个新节点public void addAtHead(int val) {ListNode newNode = new ListNode(val); // 创建新节点newNode.next = dummyHead.next; // 新节点指向当前头节点dummyHead.next = newNode; // 虚拟头节点指向新节点size++; // 更新链表大小}// 在链表尾部添加一个新节点public void addAtTail(int val) {ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到链表尾部while (curNode.next != null) {curNode = curNode.next; // 移动到下一个节点}ListNode newNode = new ListNode(val); // 创建新节点curNode.next = newNode; // 尾节点指向新节点size++; // 更新链表大小}// 在指定索引处添加一个新节点public void addAtIndex(int index, int val) {// 如果索引大于链表大小，无法添加if (index > size) {return;}// 如果索引小于 0，从头部插入if (index < 0) {index = 0;}ListNode newNode = new ListNode(val); // 创建新节点ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的前一个节点for (int i = 0; i < index; i++) {curNode = curNode.next; // 移动到下一个节点}// 插入新节点newNode.next = curNode.next; // 新节点指向当前位置的下一个节点curNode.next = newNode; // 前一个节点指向新节点size++; // 更新链表大小}// 删除指定索引的节点public void deleteAtIndex(int index) {// 检查索引是否有效if (index < 0 || index >= size) {return; // 索引无效，不进行任何操作}size--; // 先减少链表大小ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的前一个节点for (int i = 0; i < index; i++) {curNode = curNode.next; // 移动到下一个节点}// 删除目标节点curNode.next = curNode.next.next; // 前一个节点指向目标节点的下一个节点}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

双指针

反转链表

206. 反转链表 - 力扣（LeetCode）

class Solution {// 反转链表的核心方法，传入链表的头节点 headpublic ListNode reverseList(ListNode head) {// 如果链表为空或链表只有一个节点，则不需要反转，直接返回原链表的头节点if (head == null || head.next == null) {return head;  // 终止条件：空链表或只有一个节点}// 初始化两个指针：pre 用来跟踪已经反转的部分，cur 用来跟踪未反转的部分ListNode pre = head;   // pre 指向当前节点，初始时为链表的头节点ListNode cur = head.next;   // cur 指向下一个节点，初始时为头节点的下一个节点// 将头节点的 next 设为 null，因为反转后原来的头节点会成为尾节点，尾节点的 next 应该是 nullhead.next = null;// 开始遍历链表，直到 cur 为空（即链表末尾）while (cur != null) {ListNode temp = cur.next;   // 暂存 cur 的下一个节点，防止链表断开后丢失后续节点cur.next = pre;   // 将当前节点 cur 的 next 指向 pre，从而实现反转pre = cur;   // pre 前进到 cur，表示反转后的部分已经包括当前节点cur = temp;   // cur 前进到下一个节点（即之前暂存的节点），继续反转}// 当 cur 为 null 时，pre 指向的是反转后的新头节点，返回该节点return pre;}
}

两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

// 定义链表节点类
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 swapPairs(ListNode head) {// 定义一个虚拟头节点 dummyHead，用来简化链表头部的操作ListNode dummyHead = new ListNode(0);  // 虚拟头节点，值为0，指向实际链表的头节点dummyHead.next = head;  // 将虚拟头的 next 指向传入的 head，便于处理链表的开头// 定义临时指针 temp，用来遍历链表。初始指向 dummyHead，方便处理链表头部ListNode temp = dummyHead;// node1 和 node2 分别用于指向要交换的两个相邻节点ListNode node1;ListNode node2;// 只要 temp 后面有两个节点存在（即 temp.next 和 temp.next.next 都不为空），就可以继续交换while (temp.next != null && temp.next.next != null) {// node1 指向第一对中第一个节点node1 = temp.next;// node2 指向第一对中第二个节点node2 = temp.next.next;// 开始交换：将 temp 的 next 指向第二个节点（node2）temp.next = node2;// 将第一个节点 node1 的 next 指向第二个节点 node2 的下一个节点，即交换后第一个节点应该指向的节点node1.next = node2.next;// 将第二个节点 node2 的 next 指向第一个节点 node1，完成交换node2.next = node1;// 将 temp 指向 node1，继续处理下一对temp = node1;  // node1 是交换后的第二个节点，所以 temp 移动到这里准备处理下一对节点}// 返回新链表的头节点，即 dummyHead 的 nextreturn dummyHead.next;  // dummyHead 是虚拟头节点，实际链表的头节点在 dummyHead.next}
}

删除链表的倒数第N个节点

代码随想录 (programmercarl.com)

// 定义链表节点类
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 {// 移除链表中倒数第 n 个节点public ListNode removeNthFromEnd(ListNode head, int n) {// 边界检查，如果链表为空，直接返回 nullif (head == null) {return null;}// 定义一个虚拟头节点，dummyHead 用来处理链表头部的特殊情况（例如删除头节点）ListNode dummyHead = new ListNode(0);dummyHead.next = head; // dummyHead.next 指向链表头节点// 定义快指针 fast 和慢指针 slow，都初始化为 dummyHeadListNode fast = dummyHead;ListNode slow = dummyHead;// 快指针 fast 先前进 n+1 步，以便与慢指针 slow 之间的距离为 nfor (int i = 0; i <= n; i++) {fast = fast.next;}// 快慢指针同时向前移动，直到 fast 到达链表末尾while (fast != null) {fast = fast.next;slow = slow.next;}// 此时慢指针 slow 指向待删除节点的前一个节点，执行删除操作slow.next = slow.next.next;// 返回新的链表头节点（dummyHead.next），此时 dummyHead.next 是链表的头节点return dummyHead.next;}
}

哈希表

判断是否存在同一个元素

链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

public class Solution {// 定义一个方法来获取两个链表的交点节点public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 使用一个 HashSet 来存储链表 A 的所有节点Set<ListNode> hashset = new HashSet<ListNode>();// 创建一个指针 cur，用于遍历链表 AListNode cur = headA;// 遍历链表 A，直到链表的末尾while(cur != null){// 将当前节点添加到 HashSet 中hashset.add(cur);// 移动到下一个节点cur = cur.next;}// 重新使用 cur 指针遍历链表 Bcur = headB;// 遍历链表 B，直到链表的末尾while(cur != null){// 如果当前节点在 HashSet 中，说明找到了交点if(hashset.contains(cur)){// 返回交点节点return cur;}// 移动到下一个节点cur = cur.next;}// 如果没有交点，返回 nullreturn null;}
}

环形链表

142. 环形链表 II - 力扣（LeetCode）

public class Solution {public ListNode detectCycle(ListNode head) {// 创建一个 HashSet 用来存储访问过的节点Set<ListNode> hashset = new HashSet<>();// 初始化当前节点为链表的头节点ListNode cur = head;// 循环遍历整个链表while (cur != null) {// 如果当前节点已经存在于 HashSet 中，说明链表有环，且该节点就是环的起点if (hashset.contains(cur)) {return cur;  // 返回环的起点节点} else {// 如果当前节点不在 HashSet 中，将其添加到集合中，表示已经访问过该节点hashset.add(cur);}// 移动当前指针到下一个节点cur = cur.next;}// 如果遍历完整个链表都没有找到重复的节点，说明链表无环，返回 nullreturn null;}
}

总结

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

常见的VPS或者独立服务器的控制面板推荐

常见的VPS或者独立服务器的控制面板推荐

随着越来越多的企业和个人转向VPS和独立服务器以获得更高的性能和灵活性&#xff0c;选择合适的控制面板变得尤为重要。一个好的控制面板可以大大简化服务器管理&#xff0c;提高工作效率。本篇文章将介绍2024年最值得推荐的VPS控制面板&#xff0c;帮助您做出明智的选择。 1.…
阅读更多...
python调用opencv报错“module ‘cv2‘ has no attribute ‘namedWindow‘”

python调用opencv报错“module ‘cv2‘ has no attribute ‘namedWindow‘”

之前电脑上使用pip install安装过opencv相关的python模块&#xff0c;不过后续学习opencv时主要使用OpenCVSharp在VS2022中创建项目测试。今天学习过程中突然想用python试试&#xff0c;不过运行下面代码时报错“module ‘cv2’ has no attribute namedWindow”。 import cv2c…
阅读更多...
TVS管工作原理：【图文讲解】

TVS管工作原理：【图文讲解】

TVS(Transient Voltage Suppressor)二极管&#xff0c;又称为瞬态抑制二极管&#xff0c;是普遍使用的一种新型高效电路保护器件&#xff0c;它具有极快的响应时间&#xff08;亚纳秒级&#xff09;和相当高的浪涌吸收能力。当它的两端经受瞬间的高能量冲击时&#xff0c;TVS能…
阅读更多...
每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java

每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java

目录 牛客_DP2跳台阶_动态规划 题目解析 C代码 Java代码 牛客_DP2跳台阶_动态规划 跳台阶_牛客题霸_牛客网 题目解析 当前值只和数组的前两个值有关&#xff0c;在往前面的就无关了&#xff0c;所以没必要申请一个数组&#xff0c;直接使用两个变量即可&#xff0c;这样空…
阅读更多...
【数据结构与算法】时间复杂度和空间复杂度例题

【数据结构与算法】时间复杂度和空间复杂度例题

文章目录 时间复杂度常数阶时间O(1)对数阶时间O(logN)线性阶时间O(n)线性对数阶时间O(nlogN)平方阶时间O(n*n) 空间复杂度常量空间O(1)线性空间O(n)二维空间O(n*n)递归空间 时间复杂度 常数阶时间O(1) 代码在执行的时候&#xff0c;它消耗的时间并不随着某个变量的增长而增长…
阅读更多...
pytorch之梯度累加

pytorch之梯度累加

1.什么是梯度&#xff1f; 梯度可以理解为一个多变量函数的变化率&#xff0c;它告诉我们在某一点上&#xff0c;函数的输出如何随输入的变化而变化。更直观地说&#xff0c;梯度指示了最优化方向。 在机器学习中的作用&#xff1a;在训练模型时&#xff0c;我们的目标是最小…
阅读更多...
LeetCode[中等] 279.完全平方

LeetCode[中等] 279.完全平方

给你一个整数 n &#xff0c;返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数&#xff0c;其值等于另一个整数的平方&#xff1b;换句话说&#xff0c;其值等于一个整数自乘的积。例如&#xff0c;1、4、9 和 16 都是完全平方数&#xff0c;而 3 和 11 不是。 1…
阅读更多...
数值计算的程序设计问题举例

数值计算的程序设计问题举例

### 数值计算的程序设计问题 #### 1. 结构静力分析计算 **涉及领域**&#xff1a;工程力学、建筑工程 **主要问题**&#xff1a;线性代数方程组&#xff08;Linear Algebraic Equations&#xff09; **解释说明**&#xff1a; 在结构静力分析中&#xff0c;我们需要解决复杂的…
阅读更多...
Java项目实战II基于Java+Spring Boot+MySQL的购物推荐网站的设计与实现(源码+数据库+文档)

Java项目实战II基于Java+Spring Boot+MySQL的购物推荐网站的设计与实现(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者 一、前言 随着互联网技术的飞速发展&#xff0c;电子商务已成为人们日常生活中不可或缺的一部分。然而&#xf…
阅读更多...
自动驾驶系列—自动驾驶MCU架构全方位解析：从单核到多核的选型指南与应用实例

自动驾驶系列—自动驾驶MCU架构全方位解析：从单核到多核的选型指南与应用实例

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…
阅读更多...
VIIRS 版本1（5000）数据于2024年6月17日停更，请转向VIIRS版本2（5200）

VIIRS 版本1（5000）数据于2024年6月17日停更，请转向VIIRS版本2（5200）

根据官网发布的消息&#xff0c;VIIRS版本1&#xff08;5000&#xff09;的多数数据产品于今日停止更新。需要VIIRS数据的朋友需要转向版本2数据了。 可见红外成像辐射计套件 (VIIRS) 第 1 版 (集合 1) 陆地数据产品于 2024 年 6 月 17 日终止生产。唯一的例外是双向反射分布函…
阅读更多...
python+requests接口测试（tonken）

python+requests接口测试（tonken）

一、如何提取tonken值 token案例&#xff1a; 案例&#xff1a; 网站&#xff1a;http://shop.duoceshi.com/login?redirect%2Fdashboard 验证码&#xff08;固定&#xff09;&#xff1a;8888 二、抓取接口 第一个接口&#xff1a;code接口&#xff1a;http://manage.duoc…
阅读更多...
Stm32的bootloader无法使用问题

Stm32的bootloader无法使用问题

Stm32的bootloader无法使用问题 用不了一键下载电路 首先简单地对此处涉及的内容进行介绍:如果stm32的BOOT0引脚为低电平时,系统从FLASH中启动,而如果BOOT0引脚为高电平,且BOOT1为低电平时,系统从自举程序(bootloader)中启动. 我在自制照相机设计中加入了ISP一键下载电路,如…
阅读更多...
C# 无边框窗体，加阴影效果、多组件拖动、改变大小等功能完美实现优化版效果体验

C# 无边框窗体，加阴影效果、多组件拖动、改变大小等功能完美实现优化版效果体验

一、预览效果 国庆节第一天，祝祖国繁荣昌盛！ 1.1 效果图 （WinForm无边框窗体，F11可全屏） 拖动窗体时半透明效果（拖动时参考窗体后面释放位置） 说明：本功能的实现基于网友的原型完善而来，更多代码可以参考他的文章 h
阅读更多...
html+css+js实现step进度条效果

html+css+js实现step进度条效果

实现效果 代码实现 HTML部分 <div class"box"><ul class"step"><li class"circle actives ">1</li><li class"circle">2</li><li class"circle">3</li><li class&quo…
阅读更多...
“2024光明多多垂直农业挑战赛”决赛启动成功举办

“2024光明多多垂直农业挑战赛”决赛启动成功举办

由光明食品集团所属上花集团的光明花博邨基地&#xff0c;与拼多多携手&#xff0c;联合中国农业大学、浙江大学等共同举办的“2024光明多多垂直农业挑战赛暨第四届多多农研科技大赛”于9月20-21日正式启动决赛。来自上海交大、中国农大、上海农科院、国家农业智能装备工程技术…
阅读更多...
【成神之路】Ambari实战-014-代码生命周期-metainfo-cardinality详解

【成神之路】Ambari实战-014-代码生命周期-metainfo-cardinality详解

1.Redis 集群 metainfo.xml 示例 <?xml version"1.0"?> <metainfo><schemaVersion>2.0</schemaVersion><services><service><!-- Redis 集群服务的基本信息 --><name>REDIS</name><displayName>Redi…
阅读更多...
C# HttpClient请求URL重定向后丢失Authorization认证头

C# HttpClient请求URL重定向后丢失Authorization认证头

搜查官方文档后发现&#xff1a; HttpWebRequest.AllowAutoRedirect Property (System.Net) | Microsoft Learn 微软提供的http类库HttpClient &#xff08;HttpWebRequest\WebClient已不推荐使用&#xff0c;用HttpClient代替&#xff09;有备注提醒&#xff1a;当使用自动重…
阅读更多...
vite 快速入门指南

vite 快速入门指南

相关链接 演示地址源码地址vite 官网地址 Vite 是什么 Vite 是由 Evan You&#xff08;Vue.js 创始人&#xff09;开发的现代前端构建工具&#xff0c;专为提升开发体验而设计。它通过创新的开发模式和高效的构建流程&#xff0c;极大提高了开发效率&#xff0c;尤其在处理大…
阅读更多...
2024年健康经济与大数据研讨会（HEBD 2024）2024 Seminar on Health Economics and Big Data

2024年健康经济与大数据研讨会（HEBD 2024）2024 Seminar on Health Economics and Big Data

在线投稿&#xff1a;学术会议-学术交流征稿-学术会议在线-艾思科蓝 2024年经济决策与人工智能国际学术会议 &#xff08;EDAI 2024&#xff09;将在2024年11月08-10日在广东省广州市隆重举行。大会邀请来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师…
阅读更多...
最新文章

Copyright @ 2022~2023