LeetCode_（兜兜转转还是你）浪漫的环形链表问题

✨✨所属专栏：LeetCode刷题专栏✨✨

✨✨作者主页：嶔某✨✨

第一题：

这道题的代码很简单，但是后续的一些问题在思考的过程是很复杂的。下面我们就一起来分析一下吧！

链表带环的意思就是说链表的某个节点的next指针指向了前面的某个节点（如图），当然、在极端情况下，也可能指向自己。我们在做题的时候可以将上图抽象成下图：

快慢指针：我们定义两个指针fast、slow都指向头节点，每一次循环让fast走两步，slow走一步。

（1）链表中带环：那么fast先进环，slow后进环。这时就变成了追及相遇问题了，如果最后fast指针等于slow指针，那么说明链表带环，返回true。

（2）链表中不带环：如果fast走向空指针了，说明链表不带环，返回false。所以我们以fast和fast的next不为空为循环条件。

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

那么接下来，我们思考这样一个问题：先前我们是让fast一次走两步，slow一次走一步。那如果fast一次走三步、四步、五步呢？

这里我们讨论fast一次走三步的情况：

假设当slow也进环时，fast于slow指针之间的节点个数为 N 这里就有两种情况：

（1）N为偶数：那么距离变化：N -> (N-2) -> (N-4) ->......-> 4 -> 2 -> 最后fast == slow。

（2）N为奇数：距离变化：N -> (N-2) -> (N-4) ->......->3 -> 1 -> (-1)最后还是错过了……

我们不仅追不上，在一些步数差上，我们还会在接触后渐行渐远……

我们爱的奋不顾身，殊不知，这正好让我们渐行渐远……

那么当N为奇数时，错过后就真的没有挽回的余地了吗？我们接着分析：

当fast和slow之间的距离为 -1 时，实际上它们之间的距离为： (C - 1)

（1）我们之间又开始了下一段追及相遇，同上，当 (C - 1)为偶数时，刚好追上。

（2）当 (C - 1)为奇数时就永远追不上了。因为（C - 1）为奇数，下一次我们也必然会错过，一旦错过就是万劫不复……

所以这里我们得出结论当N为奇数且C为偶数时：他们两个永远也追不上彼此。

但……真的是这样吗？或者说你真的甘心就是如此了吗？

C和N有没有可能都为奇数或者都为偶数呢？

我们不妨继续分析

假设当slow进环的时候，fast已经在环里面转了x圈了，这时fast指针走的总路程为：

L + x*C + N

而slow只走了 L 这么长的距离，由于slow每次走一步，fast每次走三步，所以fast走的路程为slow的三倍，我们得到以下关系：

3L = L + x*C + C - N

整理一下：

2L = (x+1)*C - N

等号左边为偶数，如果N为奇数，C为偶数，一个偶数减一个奇数，不可能为偶数。所以不可能同时满足N为奇数、C为偶数或者C为奇数、N为偶数。

只能是它们两个同时为奇数或者同时为偶数。

所以我们一定会再次相遇……

就算我们错过了，亲爱的，我们还会遇见的……

第二题：

这道题的代码也很简单，但是思考的过程是很复杂的，我们一起来分析一下：

这里我们要确定入环的第一个节点这里有一个O(n^2)的算法，就是将链表的每一个节点都判断一下然后让一个指针一直往后走，如果最终这个指针和此节点相等了，那么此节点就是要寻找的第一个节点。

但是此算法太过复杂，有没有更好一点的算法呢？

这里我们给出一种代码简单的算法：

struct ListNode* detectCycle(struct ListNode* head)
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* meet = fast;
            while (meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
           	return meet;
        }
	}
    return NULL;
}

我们让一个节点在快慢指针的地方开始，另一个指针从头节点开始走，它们相遇的地方就是入环的第一个节点。