哪里学做网站,如何攻击php网站,研究生网站 建设 需求,宁波seo整站优化软件文章目录 #x1f9da;什么是链表#xff08;链表概念及分类#xff09;链表分类单链表和双链表的区别 #x1f6b4;♂️单链表、双向链表的实现单链表的实现双向链表的实现 #x1f349;链表经典OJ笔试题反转单链表移除链表元素合并两个有序链表链表分割链表的中间结点… 文章目录 什么是链表链表概念及分类链表分类单链表和双链表的区别 ♂️单链表、双向链表的实现单链表的实现双向链表的实现 链表经典OJ笔试题反转单链表移除链表元素合并两个有序链表链表分割链表的中间结点环形链表环形链表 I判断链表中是否有环环形链表 II判断链表开始入环的第一个结点 复制带随机指针的链表 链表相关文章直通车 大家好我是纪宁。 这篇文章将带来完整版的链表内容的讲解。文章内容包括链表的概念、分类、单双链表的实现、链表的经典OJ题目等。每一个专题中讲解了相应问题实现思路及方法当然实际解决过程中肯定也会出现各种各样的小问题记录每个问题具体实现方法和代码的文章链表在每个专题的末尾点击即可进入。其次文章末尾也提供了上述所有问题链接的合集供大家前往参考学习。 什么是链表链表概念及分类
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。非连续的意思就是链表的每一部分可以在内存的任意一块区域存在且这块区域的地址是随机的所以一般用动态内存来开辟这块空间的地址。而链表的每一部分都称为一个节点每个节点分为两部分数据域和指针域通过指针域即可访问其他结点的数据。
链表分类
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 单链表的每个节点分为两部分一部分存储数据一部分存储下一个节点的地址。前一个节点中存储着下一个节点的地址这也是单链表能连起来的原因。 带头双向循环链表结构最复杂但结构最优一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。 双向链表的节点有两个指针域和一个数据域两个指针一个指向后一个节点另一个指向前一个节点数据域中存储数据。默认双向链表都是有带哨兵位的头节点哨兵位的头节点中储存着第一个有效节点的地址phead-next和最后一个有效节点的地址phead-prev。 除了上面两个最常用的链表之外还有无头单向循环链表、带头单向循环链表、带头单向不循环链表、无头双向循环链表等等总之可以将是否带头、是否循环、单双向这三个条件排列组合另外还会有一些另类的复杂列表文末会举出例子。
单链表和双链表的区别 单链表的指针域中只有一个地址指向的是下一个结点的地址。而双链表的指针域中有两个地址前一个结点的地址和后一个结点的地址。 单链表找尾结点比较麻烦需要遍历而双链表找尾结点只需要找头结点的上一个结点即可。 单链表只要一直往后遍历就会遇到空指针结束而双向链表则可能会难以控制循环结束的条件而死循环下去。 单链表中一般默认没有哨兵位的头结点而双链表中默认头结点里面存的是最后一个结点和第一个有效结点的地址。 逻辑图对比 物理图对比
♂️单链表、双向链表的实现
将链表中的数据类型重定义为某种类型并定义一个链表节点的结构体其中节点的数据域是当前节点的数据另一部分则是地址。即将链表的数据域和指针域放在一个结构体中且链表中存储的数据最好是可变的每生成一个链表都要单独开辟额外的空间。
单链表的实现
每开辟一个结点的空间都要为这个结点的数据域赋值并让它的指针域指向NULL。单链表的头插头删都要传二级指针因为要改变头插头删都要改变头指针的指向删除某一结点需要先找到这个结点的上一个结点必要时候要用另一个结点保存某个结点的地址防止地址丢失的情况。 具体实现方式单链表的实现
双向链表的实现
双向链表在开辟结点时要先将结点的指针域置空当确定结点位置时再将结点的两个指针域指向应指向的结点。 具体实现方式双链表的实现
链表经典OJ笔试题
反转单链表 思路是用三个指针从前到后一次改变每个结点的指向。 题目及详解反转单链表
移除链表元素 定义两个指针保证从第二个结点开始一个指针在另一个指针的后面这样就能在不丢失数据的情况下移除链表某结点。 题目及详解移除链表元素
合并两个有序链表 将两个链表的节点逐个比较小的尾插到新链表的后面每次尾插完新链表和较小值的链表的指针都要向前走有一个为空就停止循环最后再将那个不为空的链表节点全部尾插到新链表。 这道题最好的思路是构建一个哨兵位来实现尾插不构建哨兵位也可以但需要考虑更多的边界条件。 题目及详解合并两个有序链表
链表分割
现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 如图给定的链表为 4-5-3-1-2-7 给一定值为 3分割后的值为 1-2-4-5-3-7 此题最好的解决方法是开辟两个哨兵位的头结点将这两两部分的数据按要求一次尾插到两个哨兵位的后面再将较小的一部分的尾结点指向较大部分的第一个结点将较大部分的最后一个结点置空最后将两个哨兵位释放返回较小部分的第一个结点的地址即可。 题目及详解链表分割
链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 此题知识点快慢指针 控制两个指针快指针每次向前走两步步慢指针每次向前走一步当快指针走到尾部的时候慢指针则刚好走到中间结点。 题目及详解链表的中间结点
环形链表
环形链表中用到了快慢指针和追及问题相关知识带点。
环形链表 I判断链表中是否有环
环形链表 II判断链表开始入环的第一个结点
环形链表I、II 题目及详解环形链表
复制带随机指针的链表
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。 复制后的链表相关位置的索引必须和原链表一模一样。 题目思路
拷贝所有节点每个结点放在对应原节点的后面。将每个 random 指向对应的位置。将复制的链表解下来尾插到一起并将原链表恢复。 题目及详解复制带随机指针的链表
链表相关文章直通车
单链表的实现 双链表的实现 反转单链表 移除链表元素 合并两个有序链表 链表分割 链表的中间结点 环形链表 复制带随机指针的链表
