142. Linked List Cycle II

题目链接: https://leetcode.com/problems/linked-list-cycle-ii/description/

---

题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

分析

这道题知乎面试的时候问到了，当时比较蠢，以为这个问题很复杂….

现在回头来看其实非常简单，p1是慢指针，p2是快指针。

p1每次走一步，p2每次走两步

如果有环的话，那么p1迟早会和p2相遇的。

---

• 假定
  假定：相遇的时候，p1已经走了k步，那p2就已经走了2k步

没入环之前走了a步

p1肯定是第一环都没走完(假定已经走了m步吧)

p2已经走了 r(环长) + m 只能是一圈，这里可以想想

---

• 整理一下

p1 -> a + m = k
p2 -> a + r +m = 2k

-> a = r - m

所以从起点开始到 入环点的距离，跟相遇点到入环点的距离相同。

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (head == NULL || head->next == NULL)
			return NULL;
		// 快慢指针
		ListNode *p1 = head->next, *p2 = head->next->next, *p3 = head;
		// 默认无环
		int flag = 0;
		// 若不是环，那么p2会指向NULL
		while (p2&&p1&&p2->next) {
			if (p2 != p1) {
				p2 = p2->next->next;
				p1 = p1->next;
			}
			else {
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			return NULL;
		}
		else {
			while (p1 != p3) {
				p1 = p1->next;
				p3 = p3->next;
			}
			return p3;
		}
	}
};