一个月速刷leetcodeHOT100 day11 链表完全解析 以及链表5道easy题

2024-05-27 06:04
文章标签 链表 解析 day11 完全 一个月 easy 速刷 leetcodehot100

本文主要是介绍一个月速刷leetcodeHOT100 day11 链表完全解析 以及链表5道easy题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表

表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包活两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
更用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表的特点
1.插入、删除数据效率高（1）级别（只需更改指针指向即可），随机访问效率低O（n）级别（需要从链头至链尾遍历）。
2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针a

单链表封装

class Node {constructor(val) {this.val = val;this.next = null;}}class LinkList {constructor() {this.head = null;this.length = 0;}append(val) {let node = new Node(val);if (this.head) {let p = this.head;while (p.next) {p = p.next;}p.next = node;// val.next = this.hand;} else {this.head = node;}this.length++;}removeAt(index){if(index > 0 && index < this.length){let pre;let current = this.headif(index === 0){this.head = this.head.next}for(let i=0 ;i < index;i++){pre = currentcurrent = current.next}pre.next = current.nextthis.length--return current.val}}getNodeAt(index){if(index >= 0 && index <this.length){let node = this.headfor (let i= 0; i< index; i++) {node = node.next}return node.val}return}remove(element){let current;for (let i= 0; i< this.length; i++) {if(element === this.getNodeAt(index)){return i}current = current.next}return -1}insert(element,index){if(index >=0 && index< this.length){let node = new Node(element)if(index === 0){let cur = this.headthis.head = nodenode.next = cur}else{for(let i = 0 ;i < this.length; i++){let pre = getNodeAt(index -1)let cur = pre.nextnode.next = curpre.next = node}}this.length--return true}return false}isEmpty(){return this.length === 0}size(){return this.length}getHead(){return this.head}print() {let p = this.head;let str = "";if (p) {do {str += p.val + " -> ";p = p.next;} while (p.next);{str += p.val;console.log(str);}} else {console.log("空链表");}}}

双向链表

节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指next）。

  class Node {constructor(val){this.val = valthis.next = nullthis.prev = null}}class NodeList{constructor() {this.head = null;this.tail =null;this.length = 0;}push(val){let node = new Node(val)if(this.head === null){this.head = nodethis.tail = node}else{this.tail.next = nodenode.prev = this.tailthis.tail = node}this.length++}insert(val,index){if(index >= 0 && index <= this.length){let node = new Node(val)let current= this.headif(index === 0){if(this.head === null){this.head = nodethis.tail = node}else{node.next = this.headthis.head.prev = nodethis.head = node}}else if(index === this.length){current = this.tailcurrent.next = nodenode.prev = currentthis.tail = node}else{const previous = this.getNodeAt(index -1)current = previous.nextnode.next = currentcurrent.prev = nodeprevious.next= nodenode.prev= prev}this.length++return true}}removeAt(index){if(index >= 0 && index <= this.length){let current = this.headif(index === 0){this.head = current.nextif(this.length === 1){this.tail = null}else{this.head.prev = null}}else if(index ===this.length - 1){current = this.tailthis.tail =current.prevthis.tail.next = null}else{let previous = this.getNodeAt(index -1)current = previous.nextprevious.next = current.nextcurrent.next.prev = previous}this.length--;return current.element}}}

循环链表封装

环链表和链表之间准一的区别在于，最后一个元素指向下 元素的指针（tail.next）不是引用undefined，而是指向第一个元素（head）

 class Node {constructor(val){this.val = valthis.next = null}}class circleLinklist {constructor(){this.head = nullthis.length = 0;}push(val){let node= new Node(val)if(this.length === 0){this.head = node}else{let current = getNodeAt(this.size()-1)current.next = node}node.next = this.headthis.length++}insert(val,index){if(index>=0&& index<=this.count){const node = new Node(val)let current = this.headif(index === 0){if(this.head === null){this.hand = nodenode.next = this.head}else{node.next = current//获取最后一个元素current = this.getNodeAt(this.size() - 1)this.head = nodecurrent.next = this.head}}else{const previous = this.getNodeAt(index -1)node.next = previous.nextprevious.next = node}this.length++return true}return false}removeAt(index){if(index >= 0 && index< this.length){let current = this.headif(index === 0){if(this.size() === 1){this.head = undefined}else{let last = this.getNodeat(this.size() -1)this.head = this.head.nextlast.next = this.head}}else{const previous = this.getNodeAt(index -1)current = previous.nextprevious.next = current.next}this.count--return current.val}}size(){return this.length}}

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

**输入：**intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
**输出：**Intersected at ‘8’
**解释：**相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

**输入：**intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
**输出：**Intersected at ‘2’
**解释：**相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

**输入：**intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
**输出：**null
**解释：**从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
思路：遍历两个链表,遇到相同值则返回

var getIntersectionNode = function(headA, headB) {const visited = new Set();let temp = headA;while (temp !== null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp !== null) {if (visited.has(temp)) {return temp;}temp = temp.next;}return null;};

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

**输入：**head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

**输入：**head = [1,2]
输出：[2,1]

示例 3：

**输入：**head = []
输出：[]
思路：将当前节点的 next\textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
思路：改变链表的next指针的指向，直接将链表反转

var reverseList = function(head) {if(!head || !head.next) return head;let temp = null, pre = null, cur = head;while(cur) {temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
};

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

**输入：**head = [1,2,2,1]
**输出：**true

示例 2：

**输入：**head = [1,2]
**输出：**false
思路:遍历然后对比

var isPalindrome = function(head) {let arr = []while (head) {arr.push(head.val)head = head.next}for (let i = 0, j = arr.length -1 ;i < j; i++, j--) {if (arr[i] !== arr[j]) {return false}}
return true};

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

**输入：**head = [3,2,0,-4], pos = 1
**输出：**true
**解释：**链表中有一个环，其尾部连接到第二个节点。

示例 2：

**输入：**head = [1,2], pos = 0
**输出：**true
**解释：**链表中有一个环，其尾部连接到第一个节点。

示例 3：

**输入：**head = [1], pos = -1
**输出：**false
**解释：**链表中没有环。
思路：用set存储 碰见相同值则返回

var hasCycle = function(head) {const set = new Set();while(head) {if(set.has(head)) return true;set.add(head);head = head.next;}return false;};

合并两个有序链表

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

**输入：**l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

**输入：**l1 = [], l2 = []
输出：[]

示例 3：

**输入：**l1 = [], l2 = [0]
输出：[0]
思路:代码比较l1和l2头节点的值。如果l1的值小于l2的值，那么将l1的next指针指向递归调用mergeTwoLists函数的结果，其中l1.next作为新的l1传入，而l2保持不变。然后返回l1。
如果l1的值大于等于l2的值，那么将l2的next指针指向递归调用mergeTwoLists函数的结果，其中l2.next作为新的l2传入，而l1保持不变。然后返回l2。

var mergeTwoLists = function(l1, l2) {if(l1 === null){return l2;}if(l2 === null){return l1;}if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);return l1;}else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};

这篇关于一个月速刷leetcodeHOT100 day11 链表完全解析 以及链表5道easy题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1006666。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
HDU 2159 二维完全背包

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
zoj 1721 判断2条线段（完全）相交

zoj 1721 判断2条线段（完全）相交

给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2