有趣例题|力扣 142.环形链表算法|链表|linq|leetcode

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
做题链接：142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)
推荐先看：力扣 141.环形链表_i跑跑的博客-CSDN博客
【有趣例题|力扣 142.环形链表】目录
题目：
思路 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 (inext; } //一起走 while (len != sht) { len = len->next; sht = sht->next; } return len; } } return NULL; }