[数据结构与算法]力扣 142.环形链表

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

做题链接：142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

推荐先看：?力扣 141.环形链表_i跑跑的博客-CSDN博客?

目录

题目：

思路 1：

推到如下：

代码如下：?

思路2：?

图解：?

代码：?

题目：

思路 1：

快慢指针，slow一次一步，fast一次两步，找到相遇点，再用两个指针，一个从相遇点开始走，一个从头结点开始走，两个指针相等时，则他们两个为链表入环的第一个结点。

这个方法肯定正确，但得推到，不然是很懵的。

推到如下：

由公式可证明上述思路1的可行性

代码如下：?

struct ListNode *detectCycle(struct ListNode *head) {
	struct ListNode* first, *slow;
	first = slow = head;
	//没环不可能死循环
	while (first&&first->next)
	{
		slow = slow->next;
		first = first->next->next;
		if (slow == first)
		{
			//相遇点
			struct ListNode* meet = slow;

            //公式应用
			while (meet != head)
			{
				head = head->next;
				meet = meet->next;
			}
			return meet;
		}
	}
	return NULL;
}

思路2：?

快慢指针，找遇见点，之后截断遇见点，令遇见点为另一个链表末尾，之后遇见点的next为另一个链表的开头，使整个链表变为一个相交链表，返回交点，即是入环结点。

图解：

代码：?

struct ListNode *detectCycle(struct ListNode *head) {
	struct ListNode* first, *slow;
	first = slow = head;
	//没环不可能死循环
	while (first&&first->next)
	{
		slow = slow->next;
		first = first->next->next;
		if (slow == first)
		{
			//相遇点
			struct ListNode* meet = slow;
			//新链表
			struct ListNode* newlist = meet->next;
			meet->next = NULL;
			//求出从head开始和newlist开始到共同结尾meet的长度
			struct ListNode* n1 = head;
			struct ListNode* n2 = newlist;
			int i, j;
			i = j = 0;
			while (n1)
			{
				i++;
				n1 = n1->next;
			}
			while (n2)
			{
				j++;
				n2 = n2->next;
			}
			struct ListNode* len = head;
			struct ListNode* sht = newlist;
            //判断长短链表
			if (i<j)
			{
				len = newlist;
				sht = head;
			}
			//长的链表先走差步
			int dis = abs(i - j);
			while (dis--)
			{
				len = len->next;
			}
			//一起走
			while (len != sht)
			{
				len = len->next;
				sht = sht->next;
			}
			return len;
		}

	}
	return NULL;
}