链表mark

news/2024/7/25 21:10:41/文章来源:https://blog.csdn.net/vbgesab/article/details/139280112

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

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

如图所示: 

链表1

链表的类型

接下来说一下链表的几种类型:

单链表

刚刚说的就是单链表。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示: 

链表2

循环链表

循环链表,顾名思义,就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表4

链表的存储方式

了解完链表的类型,再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

如图所示:

链表3

这个链表起始节点为2, 终止节点为7, 各个节点分布在内存的不同地址空间上,通过指针串联在一起。

链表的定义

接下来说一说链表的定义。

链表节点的定义,很多同学在面试的时候都写不好。

这是因为平时在刷leetcode的时候,链表的节点都默认定义好了,直接用就行了,所以同学们都没有注意到链表的节点是如何定义的。

而在面试的时候,一旦要自己手写链表,就写的错漏百出。

这里我给出C/C++的定义链表节点方式,如下所示:

链表的操作

删除节点

删除D节点,如图所示:

链表-删除节点

只要将C节点的next指针 指向E节点就可以了。

那有同学说了,D节点不是依然存留在内存里么?只不过是没有在这个链表里而已。

添加节点

如图所示:

链表-添加节点

可以看出链表的增添和删除都是O(1)操作,也不会影响到其他节点。

但是要注意,要是删除第五个节点,需要从头节点查找到第四个节点通过next指针进行删除操作,查找的时间复杂度是O(n)。

性能分析

再把链表的特性和数组的特性进行一个对比,如图所示:

链表-链表与数据性能对比

数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。

链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。

class ListNode:def __init__(self, val, next=None):self.val = valself.next = next

例题:

203. 移除链表元素

简单

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

提示:

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

# 定义链表节点类
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 移除链表中指定值的节点的函数
def removeElements(head: ListNode, val: int) -> ListNode:# 创建一个虚拟头节点,方便处理头节点可能被删除的情况dummy = ListNode(next=head)prev = dummy  # 前一个节点curr = head  # 当前节点while curr:  # 只要当前节点不为空if curr.val == val:  # 如果当前节点的值等于要删除的值prev.next = curr.next  # 将前一个节点的下一个指针指向当前节点的下一个else:prev = curr  # 否则,更新前一个节点curr = curr.next  # 移动到下一个节点return dummy.next  # 返回新的头节点# 示例用法
head1 = ListNode(1, ListNode(2, ListNode(6, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))))
print(removeElements(head1, 6))head2 = ListNode()
print(removeElements(head2, 1))head3 = ListNode(7, ListNode(7, ListNode(7, ListNode(7))))
print(removeElements(head3, 7))

这段代码的逻辑是:使用一个虚拟头节点 dummy 来简化处理。通过两个指针 prev(前一个节点)和 curr(当前节点)遍历链表。如果当前节点的值等于目标值,就跳过当前节点,将前一个节点的下一个指针指向当前节点的下一个;否则就更新前一个节点。最后返回虚拟头节点的下一个节点,即新的头节点。

空间复杂度为 O(1),因为只使用了固定的额外空间来存储虚拟头节点和两个指针。时间复杂度为 O(n),需要遍历整个链表一次。

707. 设计链表

中等

你可以选择使用单链表或者双链表,设计并实现自己的链表。

单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。

如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类:

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。

示例:

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在,链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示:

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 getaddAtHeadaddAtTailaddAtIndex 和 deleteAtIndex 的次数不超过 2000 。

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):# 初始化一个虚拟头节点self.dummy = ListNode()def get(self, index):""" 获取指定下标的节点值 """curr = self.dummy.nextfor _ in range(index):if not curr:return -1curr = curr.nextif curr:return curr.valreturn -1def addAtHead(self, val):""" 在头部添加节点 """new_node = ListNode(val, self.dummy.next)self.dummy.next = new_nodedef addAtTail(self, val):""" 在尾部添加节点 """curr = self.dummywhile curr.next:curr = curr.nextcurr.next = ListNode(val)def addAtIndex(self, index, val):""" 在指定下标处添加节点 """prev = self.dummyfor _ in range(index):if not prev.next:returnprev = prev.nextnew_node = ListNode(val, prev.next)prev.next = new_nodedef deleteAtIndex(self, index):""" 删除指定下标的节点 """prev = self.dummyfor _ in range(index):if not prev.next:returnprev = prev.nextif prev.next:prev.next = prev.next.next# 测试用例
myLinkedList = MyLinkedList()
myLinkedList.addAtHead(1)
myLinkedList.addAtTail(3)
myLinkedList.addAtIndex(1, 2)
print(myLinkedList.get(1))  
myLinkedList.deleteAtIndex(1)
print(myLinkedList.get(1))  

代码逻辑和方法:

  • ListNode 类定义了链表节点。
  • MyLinkedList 类中:
    • __init__ 方法初始化一个虚拟头节点,方便操作。
    • get 方法通过遍历到指定下标获取节点值,如果不存在则返回 -1
    • addAtHead 直接在虚拟头节点后添加新节点。
    • addAtTail 遍历到尾部添加节点。
    • addAtIndex 先找到要插入位置的前一个节点,然后插入新节点。
    • deleteAtIndex 找到要删除节点的前一个节点,然后进行删除。

空间复杂度:主要是节点占用的空间,为 O(n),其中 n 是节点数量。
时间复杂度:

  • get 最坏情况需要遍历整个链表,为 O(n)。
  • addAtHeadaddAtTailaddAtIndexdeleteAtIndex 通常为 O(n)(找到特定位置的过程)。

206. 反转链表

简单

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

示例 1:

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

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

1.以下是使用迭代方法反转链表的 Python 代码:

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseList(self, head):"""迭代反转链表"""prev = None  # 前一个节点初始化为空curr = head  # 当前节点从头部开始while curr:  # 只要当前节点不为空next_node = curr.next  # 保存下一个节点curr.next = prev  # 当前节点的下一个指向改为前一个节点prev = curr  # 更新前一个节点为当前节点curr = next_node  # 移动到下一个节点return prev  # 最后返回反转后的头节点# 测试用例
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5solution = Solution()
reversed_head = solution.reverseList(node1)curr = reversed_head
while curr:print(curr.val, end=" ")curr = curr.next

以上代码逻辑和方法:通过不断改变节点的指向来实现反转。用两个指针 prev 和 curr,遍历链表时,先保存下一个节点,然后将当前节点的下一个指向改为前一个节点,再更新前一个节点和移动当前节点到下一个节点。

空间复杂度:只使用了固定的额外空间来存储几个指针,所以空间复杂度为 O(1)。

时间复杂度:遍历整个链表一次,时间复杂度为 O(n)。

2.以下是使用递归方法反转链表的 Python 代码:

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseList(self, head):"""递归反转链表"""if not head or not head.next:  # 边界条件,链表为空或只有一个节点return headnew_head = self.reverseList(head.next)  # 递归反转后面的链表head.next.next = head  # 当前节点的下一个节点的下一个指向当前节点head.next = None  # 当前节点的下一个置空return new_head  # 返回反转后的头节点# 测试用例
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5solution = Solution()
reversed_head = solution.reverseList(node1)curr = reversed_head
while curr:print(curr.val, end=" ")curr = curr.next

代码逻辑和方法:递归到链表末尾,然后从后往前依次改变节点指向。

空间复杂度:由于递归调用会使用栈空间,在最坏情况下,栈空间的使用与链表长度成正比,所以空间复杂度为 O(n)。

时间复杂度:也是 O(n)。

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

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

相关文章

JRebel 激活及使用

插件下载 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 从磁盘安装下载的插件 windows下载激活服务 Releases ilanyu/ReverseProxy GitHub mac没有对应版本&#xff0c;需要Docker搭建本地激活服务 docker pull qierkang/golang-reverseproxy docker run -d -…

Steamdeck使用Windows系统游玩雪地奔驰时闪退问题解决方法

我非常喜欢雪地奔驰这款游戏&#xff0c;买sd的一部分也是为了它。可在我打开这个游戏时&#xff0c;游戏发生闪退问题。查阅了网络各个途径&#xff0c;基本没有解决方法。因此我自己分析终于解决该问题。以下是我解决问题的思路&#xff0c;仅供记录参考&#xff1a; 游戏在崩…

第97天:权限提升-Web 权限权限划分源码后台中间件第三方数据库等

前置知识 具体有哪些权限需要我们了解掌握的 后台权限&#xff0c;网站权限&#xff0c;数据库权限&#xff0c;接口权限&#xff0c;系统权限&#xff0c;域控权限等 以上常见权限获取方法简要归类说明 后台权限&#xff1a;SQL 注入,数据库备份泄露&#xff0c;默认或弱口…

[LLM-Agent]万字长文深度解析规划框架:HuggingGPT

HuggingGPT是一个结合了ChatGPT和Hugging Face平台上的各种专家模型&#xff0c;以解决复杂的AI任务&#xff0c;可以认为他是一种结合任务规划和工具调用两种Agent工作流的框架。它的工作流程主要分为以下几个步骤&#xff1a; 任务规划&#xff1a;使用ChatGPT分析用户的请求…

Vue:快速上手

一、简介 Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&#xff0c;…

selenium 学习笔记(一)

pip的安装 新建一个txt curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py 把上面的代码复制进去后&#xff0c;把后缀名改为.bat然后双击运行 当前目录会出现一个这个文件 然后在命令行pyhon get-pip.py等它下好就可以了selenium安装 需要安装到工程目…

Halcon 极坐标转换图像

一、概述 先看效果 将圆形的用极坐标转换成矩性然后再进行识别或者其他缺陷检测&#xff0c;最后在还圆到原图中 二、原理&#xff1a; halcon 圆环类缺陷检测的一种方法&#xff08;极坐标变换法&#xff09;_halcon缺口检测-CSDN博客 图像极坐标变换与反变换&#xff08;…

C# 泛型函数

1.非约束 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace MyGeneirc {public class GeneircMethod{/// <summary>/// 泛型方法解决&#xff0c;一个方法&#xff0c;满足不同参数类型…

C++算术运算和自增自减运算

一 引言 表示运算的符号称为运算符。 算术运算&#xff1b; 比较运算&#xff1b; 逻辑运算&#xff1b; 位运算&#xff1b; 1 算术运算 算术运算包括加、减、乘、除、乘方、指数、对数、三角函数、求余函数&#xff0c;这些都是算术运算。 C中用、-、*、/、%分别表示加、减…

Linux——多线程(一)

一、线程的概念 1.1线程概念 教材中的概念&#xff1a; (有问题?) 线程是进程内部的一个执行分支&#xff0c;线程是CPU调度的基本单位 之前我们讲的进程&#xff1a; 加载到内存中的程序&#x…

重学java 49 List接口

但逢良辰&#xff0c;顺颂时宜 —— 24.5.28 一、List接口 1.概述: 是collection接口的子接口 2.常见的实现类: ArrayList LinkedList Vector 二、List集合下的实现类 1.ArrayList集合的使用及源码分析 1.概述 ArrayList是List接口的实现类 2.特点 a.元素有序 —> 按照什么顺…

简单随机数据算法

文章目录 一&#xff0c;需求概述二&#xff0c;实现代码三、测试代码四、测试结果五、源码传送六、效果演示 一&#xff0c;需求概述 系统启动时&#xff0c;读取一组图片数据&#xff0c;通过接口返回给前台&#xff0c;要求&#xff1a; 图片随机相邻图片不重复 二&#…

Node.js和npm常用命令

一、Node.js简介 Node.js是一个免费、开源、跨平台的JavaScript运行时环境&#xff0c;允许开发人员创建服务器、web应用程序、命令行工具和脚本。 点击查看node.js中文官网 点击查看node.js英文官网 二、npm简介 npm(Node Package Manager)是Node.js的软件包管理器&#xff0…

三层交换机基本配置,动态路由链接

<Huawei>system-view //进入系统视图[Huawei]undo info-center enable //关日志[Huawei]vlan batch 2 3 //创建vlan2与3[Huawei]display vlan //检查[Huawei]interface GigabitEthernet 0/0/2 //进2口[Huawei-GigabitEthernet0/0/2]port link-type access //配置…

安全态势管理的六大挑战:态势感知

德迅云安全鉴于如今的安全威胁不断变幻&#xff0c;企业对实施态势管理策略至关重要&#xff0c;可以让安全团队根据需要进行安全策略的动态调整。如果企业在研究构建态势感知管理&#xff0c;需要特别关注以下六个方面的挑战。 如果企业正在使用一个或多个平台&#xff0c;那么…

如何用分立器件设计一个过流保护电路

过流保护电路是指当后级负载电流过大或者发生短路时&#xff0c;自动切断电源与后级负载&#xff0c;从而防止大电流损害电源电路&#xff0c;过流保护又叫OCP。 常见的过流保护电路有保险丝过流保护&#xff0c;集成的过流保护芯片&#xff0c;还有这种分立器件搭建的过流保护…

【vue-cli搭建vue项目的过程2.x】

vue-cli搭建vue项目 vue-cli搭建vue项目安装node安装vue-cli脚手架并创建项目安装 Ant Design Vue或element-ui(笔者使用Ant-design-vue组件&#xff0c;并全局引入)开发安装三方库包1、Package.json文件---引入如下package.json文件执行npm i或npm install命令即可下载如下依赖…

java多线程创建方式

1. 继承Thread类 这种方式是通过创建一个新的类继承自Thread类&#xff0c;并覆盖run()方法来创建线程。然后通过创建这个类的对象并调用其start()方法来启动线程。 public class MyThread extends Thread { public void run() { // 在这里定义线程的执行逻辑 …

基于小波分析和机器学习(SVM,KNN,NB,MLP)的癫痫脑电图检测(MATLAB环境)

癫痫是一种由大脑神经元突发性异常放电导致的大脑功能性障碍疾病。据世界卫生组织统计&#xff0c;全球约有7000万人患有癫痫。癫痫患者在发病时呈现肌肉抽搐、呼吸困难、意识丧失等症状。由于癫痫发作的偶然性&#xff0c;患者极有可能在高空、驾驶、游泳等危险情况下发病并丧…

SCI一区 | Matlab实现PSO-TCN-LSTM-Attention粒子群算法优化时间卷积长短期记忆神经网络融合注意力机制多变量时间序列预测

SCI一区 | Matlab实现PSO-TCN-LSTM-Attention粒子群算法优化时间卷积长短期记忆神经网络融合注意力机制多变量时间序列预测 目录 SCI一区 | Matlab实现PSO-TCN-LSTM-Attention粒子群算法优化时间卷积长短期记忆神经网络融合注意力机制多变量时间序列预测预测效果基本介绍程序设…