142. 环形链表 II

一、题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

二、示例

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

三、实现

3.1 方法1

假设：

链表头到环入口点距离 = L
环入口点到相遇点距离 = X
环的长度 = C

slow走的路程：$L+X$

fast走的路程：$L+n\ast C+X$

由于fast速度是slow的两倍，则有等式：$2\ast (L+X)=L+n\ast C+X$
解得：$L=n\ast C-X=(n-1)\ast C+C-X$

因此从链表头到环入口点距离（$L=(n-1)\ast C+C-X$）和从相遇点到环入口点距离（$C-X$）相同，只是差了 $(n-1)\ast C$ 也就是 $n-1$ 个环长。

由上可知，我们使用两个指针，一个指针从相遇点走，一个指针从链表头开始走，他们必定会在入口点相遇。

struct ListNode* detectCycle(struct ListNode* head) {
	struct ListNode* slow = head, * fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;

		// 带环 在环中相遇
		if (slow == fast)
		{
			struct ListNode* meet = slow;
			// 求入口点
			while (head != meet)
			{
				head = head->next;
				meet = meet->next;
			}

			return meet;
		}
	}

	return NULL;
}

3.2 方法2

快慢指针在环中相遇，把相遇点变成原链表的尾结点，相遇点的下一个结点变为新链表的头结点，这样求环的入口点问题，就变成了找两个链表的交点问题了。

但这会时间超时：参考代码 【求两个链表的交点-getIntersectionNode】

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
	struct ListNode* tailA = headA;
	struct ListNode* tailB = headB;

	// 1.判断是否相交 通过查看两个链表的尾结点是否相同
	int lenA = 1, lenB = 1;
	while (tailA->next)
	{
		tailA = tailA->next;
		++lenA;
	}

	while (tailB->next)
	{
		tailB = tailB->next;
		++lenB;
	}

	if (tailA != tailB)
	{
		return NULL;
	}

	// 2.找交点，让长的链表先走 差距 步
	int gap = abs(lenA - lenB);
	struct ListNode* longList = headA;
	struct ListNode* shortList = headB;
	if (lenA < lenB)
	{
		longList = headB;
		shortList = headA;
	}

	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)
	{
		slow = slow->next;
		fast = fast->next->next;

		// 带环 在环中相遇
		if (slow == fast)
		{
			struct ListNode* meet = slow;
			
			return getIntersectionNode(head, meet->next);
		}
	}

	return NULL;
}