数据结构练级之路【链表带环问题】

简介: 数据结构练级之路【链表带环问题】

一、链表带环问题的代码和几个经典的面试题(重点在于如何算入口点)

代码非常的简单,但是有几个关于带环问题的讲解就比较不好理解


1.有关链表是否带环的题目和代码


(较难且较经典)(有关链表带环的问题)(经典的引用了快慢指针的使用)(追击问题)

题目:给定一个链表,判断链表中是否有环。

意思:如果链表中有某一个结点,可以通过连续跟踪next指针再次到达,则链表中存在环,为了表示给定链表中的环,我们使用整数pos来表示链表尾链接到链表中的位置(索引从0开始),

如果pos的位置是-1.则在该链表中没有环,注意pos不作为参数进行传递,仅仅是为了标示链表的实际情况。

思路:使用快慢指针(slow和fast都从头结点开始,slow一次走一步,fast一次走两步,不带环fast就会为空,带环fast就会追上我的slow);


实现:


bool hasCycle(struct ListNode* head)//有环就返回true无环就返回false
{
  struct ListNode* fast = head;
  struct ListNode* slow = head;
  while (fast && fast->next)//这个就是一次走两步,此时就会涉及到一个奇偶的问题,所以两个条件都要进行判断
  {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast)//这步就是表示我追击到了(此时就是可以表明这个链表是带环的链表)
    {
      return true;
    }
  }
  return false;
}

2.经典的带环问题1

问题:问为什么slow走一步,fast走两步最后一定可以相遇?


解答:因为假如fast在追击slow的时候(此时的fast已经入环了,然后假设此时它们之间的距离是N),因为此时的fast每次都比slow多走一步,所以此时的距离就会从N到N-1,这样一直走下去,N肯定可以变成0,所以肯定可以找到


3.经典带环问题2

问题:问假如fast此时不走两步而是走n步,此时还一定可以找到吗?

解答:答案首先是:不可以;原因:

假如此时的fast走的是3步,距离还是N,fast每次比slow多走2步,所以此时是N-2,N-4(所以就可以显然看出此时假如N是一个奇数就不能追到,只有当N是一个偶数的时候才可能追到),所以不一定可以追到,并且如果继续往下一圈走的时候,如果此时还是没有追到(那么此时的这个fast就不可能找到slow了);因为:假如此时的N是一个奇数,然后此时就会导致fast在slow的前面(如果当我的fast在slow的前面时,此时的fast和slow的距离就发生的大改变,从小变成了最大,因为此时fast在前,所以距离就变成了环的长度-1(C-1)),所以假如C-1是一个奇数就会导致N是奇数(那么此时就又是那个道理,N是奇数就追不到),只有当C-1(N)是一个偶数时,才有可能追上,所以关键追上与追不上就是取决去(环的长度是奇数还是偶数),但是还要注意这边是有一个减1的,所以环的大小是偶数就追不到,环的大小是一个奇数就可以找到


4.如何求环的入口点?(理论解答)

第一种方法:

环的入口点的思路:一个指针从相遇点开始走,一个指针从链表头结点开始走,它们会在环的入口点相遇

为什么是这样的呢?所以下面我们就来介绍一下为什么一个指针从相遇点开始走,一个指针从链表头结点开始走,它们会在环的入口点相遇呢?


由上述的思路我们此时假设:

从头结点到入环点的距离是:L

环的长度是:C

慢指针在环中走的距离为:X

走的圈数是:N

所以此时在追上到相遇的过程中

慢指针走的距离:L+X

快指针走的距离:L+X+C 而是 L+X+N*C

又因为快指针走的路程是慢指针的2倍

所以此时就可以得到一个等式:

2 * (L+X) = L+X+N * C

变形得到:L+X=N * C

变形得到:L=N * C-X

变形得到:L=(N-1)*C+C-X

所以此时通过这个表达式,此时就可以得到 L=C-X;因为此时的N-1可以看成是一个整数倍的圈数,就可以看成是在循环,其实还是从这个位置开始

所以就得到了 L=C-X; 所以我们就证明了这句话 :一个指针从相遇点开始走,一个指针从链表头结点开始走,它们最终会在环的入口点相遇。


下面是图示:


11.jpeg


11.jpeg


具体求入口点的代码:

struct ListNode* detectCycle(struct ListNode* head)
{
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  while (fast && fast->next)
  {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast)//这个条件会成立的话就表示我链表是有环的,并且此时追到了
    {
      struct ListNode* meet = slow;
      //此时的这个循环中的结论就是由我的公式证明出来的
      while (meet != head)
      {
        meet = meet->next;
        head = head->next;
      }
      return meet;
    }
  }
  return NULL;
}

第二种方法:

就是可以先算出这个环的相遇点,然后把这个点给断开,然后就可以非常巧妙的把这个判断环的相遇点的问题给转换成求交点的问题(但是代码实现起来优点困难)


二、总结:

以上就是有关链表带环的一系列问题,建议反复画图理解

相关文章
|
11月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
174 4
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
204 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
319 25
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
359 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
291 5
|
11月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
246 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
132 2