首页
学习
活动
专区
工具
TVP
发布

链表之环形链表

不论在面试或者刷题过程中,很大概率都会遇到环形链表这种类型的题目,例如141. 环形链表 以及142. 环形链表 II等,本文主要介绍通过快慢指针法来解决此类题型,以供大家参考。...环形链表 环形链表大致样子如下图所示: image.png 快慢指针法 判断链表是否是环形链表,一般通过快慢指针法。...操作步骤 一、分别定义两个均指向头节点的指针(fast/slow); 二、快指针每次走两步,慢指针每次走一步; 三、如果链表存在环,则快慢指针一定会在环中相遇。...已判断链表有环 image.png 求入环的第一个节点 让慢指针重新指向链表的头节点,并让快慢指针同时每次只走一步 faster:5--->6--->7 slower:1--->2--->3 image.png...image.png 因此,由上面的图可知,当判断链表有环(快慢指针相遇)之后,再让快(或者慢)指针重新指向链表头节点,另外一个指针仍保持指向不变,然后让快/慢指针同时走,且每次只走一步,当他们再次相遇时

67520

链表

如图:发现链表的各个节点不一定是连续存储。 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定。 链表(带头结点) 逻辑结构示意图 ? 1....链表的应用实例 1.1 概念解读(重要) 使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。 关于下面及代码中的temp(临时对象)解析 ?...通俗的说,你有个朋友叫小明,小明有个朋友小红,小红有个朋友叫小蓝,于是 你-小明-小红-小蓝 一起组成了一条链表。只不过你前面有一个看不见的辅助指针帮你们把这条朋友链给维护好。...常见的面试题 求链表中有效节点个数 方法:获取到链表的节点的个数(如果是带头结点的链表,需求不统计头节点) 代码 /** * @param head 链表的头节点 * @return 返回有效节点的个数...== null || head.next.next == null) { return; } //定义一个辅助的指针(变量),帮助我们遍历原来的链表 HeroNode

52930
您找到你想要的搜索结果了吗?
是的
没有找到

链表

单向链表(又名单链表、线性链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过从头部开始,依序往下读取。 数据结构[编辑] 一个单向链表的节点被分成两个部分。...单向链表只可向一个方向遍历。 ? 以上来自维基百科对链表的解释,很清楚的可以看到,节点信息和存储下一个节点的地址,当然还有双链表,有前驱节点,还有后继节点。...链表的特点是插入删除非常方便,但是查找的复杂度是O(n),数组可以根据下标进行查找 O(1),但是插入和删除,需要移动多个元素O(n),下面举个例子和大家阐述一下链表的结构,通过 leetcode 解题...,深度理解链表。...; } /** * @param args */ public static void main(String[] args) { // 链表

47630

链表

在闭关刷了几天的leetcode后,我发现了一个事情,就是海贼王真好看,刷leecode太无聊了,于是乎我边刷题边看海贼王,也是这就是我效率很低的原因,刷了一些题后也相应的去看一下别人说的如何刷才是有效率的...---- 链表是什么: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。...链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。...-------摘自百度百科 通俗的讲,链表不像list或者数组那样,但是却能实现那样的功能。 为什么用链表?...self.head = Node(data[0]) p = self.head #这里的p是一个Node类型的数据,用for传入数据和指针

48230

链表中间节点搜索和快慢指针

前提 今天中午吃饭的时候刷了下技术类型的公众号,看到有前辈过了Ant的高P面试,其中有一道题考查了链表搜索位于中间的节点的算法。觉得解决方案很有趣,于是这里尝试重现一下。...复盘 我们先设定单链表的长度大于等于3,这样子比较容易分析算法。先简单假设一个长度为3的链表如下: 如果我们要访问中间节点,最终搜索到的应该是n2节点,内容就是n2。...如果链表的长度为偶数,这里假设为4,那么如下: 如果我们要访问中间节点,最终搜索到的应该是n2和n3节点,内容就是n2和n3。...*/ private T value; /** * 下一个节点的引用 */ private Node next; } 我们可以很轻易地构建一个链表如下...当快指针遍历整个链表完成的时候,慢指针刚好指向链表的中间节点。

37220

链表之环形链表

环形链表 II 等,本文主要介绍通过快慢指针法来解决此类题型,以供大家参考。 ? ? 环形链表 环形链表大致样子如下图所示: ? ? ? 快慢指针法 判断链表是否是环形链表,一般通过快慢指针法。...操作步骤 一、分别定义两个均指向头节点的指针(fast/slow); 二、快指针每次走两步,慢指针每次走一步; 三、如果链表存在环,则快慢指针一定会在环中相遇。 ?...思路 本题除了需要判断链表是否有环外,如果有环还要求入环的第一个节点,因此是上一个题目的升级版本,还是以快慢指针中举例的那个链表作为示例,下图将描述当链表有环的时候,如何求出入环的第一个节点,见下图示:...已判断链表有环 ? 求入环的第一个节点 让慢指针重新指向链表的头节点,并让快慢指针同时每次只走一步 faster:5--->6--->7 slower:1--->2--->3 ?...因此,由上面的图可知,当判断链表有环(快慢指针相遇)之后,再让快(或者慢)指针重新指向链表头节点,另外一个指针仍保持指向不变,然后让快/慢指针同时走,且每次只走一步,当他们再次相遇时,此时相遇的节点就是入环的第一个节点

47020

链表

‘头指针(也成为头节点)’,150是指向表格中第五行的‘地址为150’的a1节点。而‘next域’110指向 a2节点 小结 1.链表是以节点方式来存储,是链式存储。...链表介绍 链表(带头节点)逻辑结构示意图如下: 最后一个节点的‘next域’为空。 链表的应用 使用带head头的单项链表实现,对数据的增删改查操作。...(如果这个位置被占用,则添加失败并给出提示) 代码实现思路: 添加(创建) 1.先创建一个head头节点,作用就是表示链表的头 2.后面我们每加一个节点,就直接假如到链表的最后 遍历: 1.通过一个辅助变量遍历...,帮助遍历整个链表 数据结构定义 public class DataNode { public int Id { get; set; } public string Name { get...; list.Update(newNode); list.List(); } } 3.删除 从链表删除一个节点的思路 1.先找到需要删除的节点的,前一个节点temp

28110

链表

n个结点(ai(1<= i <= n )的存储映像)链结成一个链表,即为线性表(a1,a2,...,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表链表。     ...; 假设L是LinkList型的变量,则L为链表的头指针,它指向表中第一个结点。...由此,在链表中,取得第i个数据元素必须从头指针出发寻找。链表是非随机存取的存储结构。...假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x,已知p为其链表存储结构中指向结点a的指针,如图a所示。 ? 为插入数据元素x,首先要生成一个数据域为x的结点,然后插入在链表中。...可见,在已知链表中元素插入或删除的确切位置的情况下,在链表中插入或删除一个结点时,仅需修改指针而不需要移动元素。

89950

数据结构(05)_链表01(链表、静态链表、单向循环链表

链式存储结构的逻辑结构:   1.2.链表   链表中的节点定义: 注意:这里的struct是用来定义一个类,与class的访问属性相反,默认为public链表的内部结构:头节点在链表中的意义是...1.3.链表的插入与删除:   插入:    node->value = e; node->next = current->next; Current->next = node...;   删除:    toDel = current->next; current->next = toDel->nex; delete toDel;   2.链表的实现...; } return ret; }   隐患:    L;// 抛出异常,分析为什么我们没有定义 Test 对象,但确抛出了异常原因在于链表头节点构造时会调用泛指类型的构造函数...22.3 链表的最终实现    template class LinkList : public List { protected: int m_length

22010
领券