LeetCode.141——环形链表：

题目如下：

通过题目中对于环形链表的大体描述，可以知道，环形链表最后一个结点保存了一个地址，用于返回链表中某个结点。并且。这个返回的结点并不是返回图中保存数据 $2$ 的结点。而是返回链表中任意一个结点。即：

或者：

题目中给了两个要求，分别是：

1. 判断链表中是否有环

2. 如果不存在环，则返回 $false$ ，存在环则返回 $true$ 。

对于不存在环的这种情况很好判断。如果链表中任意一个结点保存的地址为 $NULL$ ,则这个链表不带环。但是难点在于如何判断链表带环。如果按照判断不带环的思想去判断是否带环，即链表是否可以无限运行下去显然不可能。

如果采用双指针的方法一个指针 $cur1$ 从头结点开始，另一个指针 $cur2$ 向后遍历，如果存在 $cur1->next == cur2-> next;$ 则说明存在结点。否则就让 $cur1$ 指向下一个结点的方法，也不能实现目的。因为带环链表按照上面的方法进行遍历时，因为带环链表中不存在存储 $NULL$ 的结点。所以一旦开始遍历，也会造成死循环。

虽然上面给出的两种方法均不能解答题目。但是，第二种方法中，对比两个指针所指向的结点中保存的地址是否相等的思路是正确的。

在上一篇文章LeetCode——单链表相关题目（持续更新）_起床写代码啦！的博客-CSDN博客

中对于寻找链表中间结点时，用到了一个方法，及创建两个指针变量 $slow$ , $fast$ ，让 $fast$ 每次向后遍历 $2$ 个结点， $slow$ 每次向后遍历 $1$ 个结点。让两个指针变量所在链表中结点的位置形成一个差值。这个方法恰好可以用来解决本题。

为了方便后续进行画图演示，将环形链表用下方的图形进行表示：

其中 $head$ 表示这个链表的头结点， $start$ 表示进入环的第一个结点。 $meet$ 表示 $slow$ ， $fast$ 这两个指针在环中相遇的结点。

将上面所提供的思路进行如下总结：

1.题目的两个要求中，返回 $false$ 的情况是不存在环，也就是说链表中有某个结点存储的地址为 $NULL$ 。对于返回 $true$ ，判断条件就是 $slow$ ， $fast$ 这两个指针中存储的地址是同一个。所以，可以将解决题目的重点放在如何找到两个指针相遇的结点，也i就是 $meet$ 。

2.对于如何寻找 $meet$ ，前面给出了方法，创建不同的指针，每个指针每次向后遍历的结点数是不同的。如果遇到两个指针中存储的地址相等。则说明找到了 $meet$ 。但是，对于上面给出的方法，会引出一个问题，即这两个指针在环形链表中是否会一定相遇的问题。下面将对这个问题进行探究

$slow$ ， $fast$ 这两个指针步数差为任意值时，是否一定会在环形链表中相遇（重点）：

按照文章上面所规定的： $slow$ 每次向后访问一个结点。 $fast$ 每次向后访问两个结点，当 $fast$ 恰好进入环的起始结点时， $slow$ 的位置大致如下：

当 $slow$ 恰好位于环的起始位置时， $fast$ 的位置大致如下：

此时， $fast$ 开始追赶 $slow$ 。假设，两个指针中间的距离，即红线所标出的距离为 $n$ 。两个指针每向后按照自己的速度遍历一次，两个指针之间的距离就会缩短 $1$ .所以，无论这个距离是奇数还是偶数。都可以找到 $meet$ 这个结点，即两个指针指向的结点保存的地址相同。

在判断链表是否有环时，对于有环的链表，两个指针会一直按照规定运动下去。对于无环的链表，会存在结点数为奇数和结点数为偶数两种情况。下面给出不带环链表对于这两种情况下，循环是否执行的判定。

（注：上述推论只是局限于一个每次访问一个结点，一个每次访问两个结点的特殊情况。对于更加严格的推论会在本文下方LeetCode.142中详细展开）

对于结点数为奇数的情况下：

如图所示，当结点数量为奇数且这个奇数 $>=3$ 时，指针走完这个链表所需要的次数永远是偶数。所以对于结点数量为奇数的链表。指针 $fast$ 每次向后访问，都有可能恰好访问到链表的最后一个结点。所以需要检测已经被访问的结点中存储地址是否为 $NULL$ 即可。即 $fast -> next$ ;

对于结点数为偶数的情况下：

如果像结点数为奇数的情况下去判断结点数量为偶数的链表，可以从图上看到，当结点数 $=2$ 时，判定为是没有环的。当数量 $>2$ 且为偶数时，每执行一次 $fast -> next -> next$ ，后面总是会剩下一个结点。再向后执行一次 $fast -> next -> next$ ，此时的 $fast$ 为 $NULL$ ，所以，偶数结点的情况下，指针是有可能访问到 $NULL$ 的，因此只需要判定 $fast$ 是否为空即可。

将上面的过程用代码表示，即：

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

执行结果如下：

LeetCode.142——环形链表Ⅱ：

(重点）探讨访问结点数不同的两个指针是否一定可以在环形链表中相遇：

如上图所示的一个环形链表，创建 $slow$ , $fast$ 两个指针，其中 $slow$ 每次向后面访问一个结点。 $fast$ 每次向后面访问三个结点。所以，两个指针每按照自己的速度向后进行一次访问，就会拉开两个结点的距离。当 $slow$ 恰好走好环的起点，即： $start$ 时，两个指针所在的位置差不多由下面的图来表示：
因为 $fast$ 的访问速度大于 $slow$ ，所以，可以上图理解成一个追赶问题。将两个指针之间用红线画出的距离用 $M$ 表示。所以，两个指针同时运动一次，距离就会变成 $M-2$ 。

假设 $M$ 是一个偶数，则，两个指针同时追赶 $n$ 次后，二者之间的距离会变成 $M-2*n$ ，并且一定会出现距离为 $0$ 的情况，即两个指针同时在 $meet$ 点。

假设 $M$ 为奇数，则，两个指针同时追赶 $n$ 次后，二者之间的距离会变成 $M-2*n$ ，但并不会出现二者之间距离为 $0$ 的情况。而是会出现 $M = 1,M = -1$ 的情况。即一个是 $fast$ 慢于 $slow$ 一个结点的距离，一个是 $fast$ 快于 $slow$ 一个结点的距离。对于 $M = -1$ 的情况，可以由下面的图像表示：

假设，整个环的长度为 $C$ ，则图中用蓝色线所标出的两个指针之间的距离就变成 $C-1$ 。

假设， $C-1$ 为偶数，则会重复 $M$ 为偶数的情况。两个指针会相遇。

假设， $C-1$ 为奇数，则会重复 $M$ 为奇数的情况。两个指针不会相遇，而是无限循环两个指针之间的距离为 $1$ 的情况。

假设 $slow$ 每次向后访问一个结点， $fast$ 向后访问4个结点。两个指针同时向后访问，两个指针之间的距离差是 $3$ 个结点的长度。对于两个指针会不会相遇的问题，就需要分成 $M$ % $3 == 0$ , $M$ % $3 == 1$ , $M$ % $3 == 2$ 三个情况来谈论。方法与上面的类型，不再展开叙述。

前面说到，当 $slow$ 每次向后访问一个结点， $fast$ 每次访问两个结点时，二者一定可以在环内相遇。又因为在相同的访问次数下 $fast$ 所访问的结点，是 $slow$ 的两倍。如果用距离来表示访问的结点的数量，上面的话也可以理解为，在相同的时间里， $fast$ 所走过的距离是 $slow$ 走过距离的两倍。当二者恰好在 $meet$ 相遇时，即：

用 $L$ 来表示头结点到环入口结点的距离，用 $X$ 表示环入口结点到 $meet$ 的距离。

此时，指针 $slow$ 所走过的距离可以表示为 $L+X$ ,指针 $fast$ 所走过的距离可以表示为 $L+N+X$ 。又因为上面说到， $fast$ 走过的距离是 $slow$ 走过距离的两倍，所以 $2(L+X) = L+C+X$ ,化简后可得： $L = C - X$ 。但是，如果当环的长度 $C$ 远小于 $L$ 时，本式不成立。此时：

若环的长度 $C$ 远小于 $L$ 时，当 $slow$ 位于 $L/2$ 时， $fast$ 恰好位于环的起点。即：

当 $slow$ 恰好走到环的起点时，此时因为 $L >>C$ ,所以， $fast$ 已经走过 $n$ 个 $C$ ，因此。当二者在 $meet$ 相遇时，二至所走过的距离可以表示为：

$2(L+X) = L+n*C+X$

化简后可得：
$L = n*C-X$

为了便于理解上述公式的含义，可以进一步化简为：

$L = (n-1)C +C-X$

其中，根据上面给出的图像，可以得出上述公式所表达的含义，即：当一个指针一次访问一个结点，另一个指针一次访问两个结点的前提下，一个结点从头结点走到环入口点 $start$ 的距离 $L$ ，恰好等于另一个指针从 $meet$ 点走向 $start$ 点的距离，即：一个指针从头指针出发，一个指针从 $meet$ 点出发，二至一定会在 $start$ 点相遇。在解决这个题目时，将会用这个结论：

题目如下：

思路一：

题目要求返回入环的第一个结点，即返回上面图中的 $start$ 点。通过上面给出的结论。即：一个指针从头指针出发，一个指针从 $meet$ 点出发，二至一定会在 $start$ 点相遇。可以得到解决题目的方法：

1. 找到两个指针在环中相遇的 $meet$ 点。

2.让头指针 $head$ 和在 $meet$ 点的 $slow$ 同时向后遍历，二者相遇的那个点就是入环的第一个结点。

代码表示为：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while( fast && fast -> next)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
        if( slow == fast)//存在相遇点，两个指针相遇
        {
            struct ListNode* meet = slow;
            while( head != meet)
            {
                meet = meet -> next;
                head = head -> next;
            }
            return meet;
        }
    }
    return NULL;  
}

执行结果如下：

思路二：

如果当两个指针在 $meet$ 点相遇后，取 $meet->next$ ，用 $newnode$ 来表示这个点。即 $meet$ 后的一个点。并且让结点 $meet$ 与后面的点断开链接，即： $meet -> next = NULL$ ,此时的链表可以用下图表示：

再对上面的图片进行更改，即：

通过对图像的改进，可以题目改进为上篇文章LeetCode——单链表相关题目（持续更新）_起床写代码啦！的博客-CSDN博客中的寻找相交结点问题。这里只给出代码，不过多解释：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA,*curB = headB;
    int lenA = 0,lenB = 0;
    //计算headA为开头的链表的长度及最后的结点地址
    while( curA -> next)
    {
        curA= curA -> next;
        lenA++;
    }
    //计算headB为开头的链表的长度及最后的结点地址
    while( curB -> next)
    {
        curB = curB -> next;
        lenB++;
    }

    //检查两个链表最后一个结点的地址是否相等。相等则说明有交点
    if( curA != curB)
    {
        return NULL;
    }
    
    //计算lenA和lenB的绝对值差值
    int gap = abs( lenA - lenB);

    //检查lenA和lenB哪个更长
    struct ListNode* longlist,*shortlist;
    if( lenA > lenB)
    {
        longlist = headA;
        shortlist = headB;
    }
    else
    {
        longlist = headB;
        shortlist = headA;
    }

    //longlist先走gap步
    while( gap--)
    {
        longlist = longlist -> next;
    }

    //上下链表的起点位置没有结点数差，再一起遍历，寻找相交点
    while( longlist != shortlist)
    {
        longlist = longlist -> next;
        shortlist = shortlist -> next;
    }
    return longlist;
    
}

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *fast = head;
    while( fast && fast -> next)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
        if( slow == fast)//存在相遇点，两个指针相遇
        {
            struct ListNode* meet = slow;
            struct ListNode* newhead = meet->next;
            meet->next = NULL;
            return getIntersectionNode(newhead,head); 
        }
    }
    return NULL;
    
}