C语言 [力扣]详解环形链表和环形链表II

各位友友们，好久不见呀！又到了我们相遇的时候，每次相遇都是一种缘分。但我更加希望我的文章index.php/tags-653.html" class="superseo">可以帮助到大家。下面就来具体看看今天所要讲的题目。

文章目录

• 1.环形链表
• 2.环形链表II

  1.环形链表

  题目描述:https://leetcode.cn/problems/linked-list-cycle/description/

  这道题目呢,现阶段使用C语言的最优方案就是使用快慢指针的方法。下面就让我给大家介绍如何使用快慢指针的方法来解决这道题目。

  我们假设让快指针一次走两步，慢指针一次走一步。下面我将用图来更直观描述此题的逻辑。

  1.当fast指针准备进环时,slow指针才走了fast指针的一半。

  

  2.当slow指针准备进环时，fast指针已经在环内转了几圈了。

  

  3.当slow指针进环时，fast指针就开始追击slow指针

  

  走到这里，这道题目实际上就变成了追击问题。当fast指针追上slow指针时，说明该链表是带环链表。反之则为不带环链表。

  思路清晰，下面请看代码实现：

  bool hasCycle(struct ListNode *head) {
      struct ListNode* fast = head,*slow = head;
      while(fast && fast -> next)
      {
          fast = fast -> next ->next;
          slow = slow ->next;
          if(slow == fast)
          {
              return true;
          }
      }
      return false;
  }
  

  其实，这道题目还有两个问题：

  1：为什么两个指针一定会相遇？有没有可能会错过，或者永远追不上？

  2：当slow走一步时，可不可以让fast指针一次走3步或者其它的步数呢？

  下面就根据以上两个问题分别讨论一下

  1.我们假设slow进环时，slow跟fast的距离为N

  

  当fast开始追击slow的时候，它们之间的距离变成N-1、N-2…直到0。说明它们每追击一次，它们之间的距离就缩小1，而距离为0时则它们相遇。

  2.我们假设分析一下slow指针一次走一步，fast指针一步走三步的情况

  1）当slow走了三分之一时，fast指针已经准备开始进环了。

  

  2.当slow指针走了三分之二时，fast指针已经在环内转了几圈了。

  

  3.当slow指针准备进环时，fast指针又在环内转了不知道多少圈

  

  我们还是假设slow指针进环时,fast指针和slow指针的距离为N

  

  当fast指针开始追击slow指针时,它们的距离变化为:N-2、N-4、…

  到这里，就有两种情况产生：

  ①当N为偶数时:则最终的距离会变成0,则说明他们相遇

  ②当N为奇数时:则最终的距离会变成-1,则说明它们错过了,进入新一轮的追击。

  我们假设C代表环的长度，那么新一轮追击的距离就变成C-1了。

  这里又有两种情况：

  1)当C-1为偶数时:则来到第①这种情况,最后会追上。

  2)当C-1为奇数时:则来到第②这种情况,它们将永远错过,无法相遇,陷入***循环。

  那么当C为偶数，N为奇数时，则说明它们无法相遇，是否会有这种情况发生呢？

  

  我们假设当slow指针准备进入环时，slow指针走过的距离为L，fast指针走过的距离为L + xC + C-N。因此，我们会产生一条等式：

  3L = L + xC + C - N 化简就变为: 2L = (x+1)*C - N

  偶数 = (x+1) × 偶数 - 奇数 ? 这显然等式不成立,则说明不可能存在C为偶数,N为奇数的这种情况,即不存在追不上的这种情况。

  讨论完fast指针走三步的情况,那么fast指针走n步的情况也跟以上的方法类似,只不讨论的过程会更加繁琐一点。

  2.环形链表II

  题目描述:https://leetcode.cn/problems/linked-list-cycle-ii/description/

  这一道题目的解法也是用快慢指针这一方法。

  想要找到入口点，最简单的办法就是让一个指针从头开始走，一个指针从fast指针和slow指针相遇的位置开始走，当两个指针相遇时，则找到入口点。

  

  代码展示：

  struct ListNode *detectCycle(struct ListNode *head) {
      struct ListNode* fast = head,*slow = head;
      while(fast && fast->next)
      {
          fast = fast -> next -> next;
          slow = slow -> next;
          //如果相遇了
          if(slow == fast)
          {
              struct ListNode* meet = slow;
              while(meet != head)
              {
                  meet = meet -> next;
                  head = head -> next;
              }
              return meet;
          }
      }
      return NULL;
  }
  

  现在又有一个问题：为什么入口点就在那个地方呢？下面就对其进行证明：

  

  假设从头开始走到入口点的距离为L，slow进环走的距离为N，环形链表的长度为C

  那么当fast指针和slow指针相遇时：

  fast指针走过的路程为: L + xC +N (x>=1的整数)

  slow指针走过的路程为: L + N

  因此我们得到一条等式: 2(L + N) = L + xC +N (x>=1)

  化简得: L = x*C - N,便于观察,我们可以将等式变为 L = (x-1)*C + C - N

  因此,不管x的值为多少,只需让相遇点多走C - N的距离,就能说明head指针和meet指针相遇,从而找到入口点。

  今天的分享就到这里啦，如果感觉内容不错，记得一键三连噢。创作不易，感谢大家的支持，我们下次再见！ヾ(￣▽￣)ByeBye