一.题目及剖析
https://leetcode.cn/problems/linked-list-cycle-ii/description/
这道题就是找到链表中环的入口
二.思路引入
假设起点到环的入口的距离为L, 环的长度为C, 入口到相遇点的距离为C - N
设定一个快慢指针,速度分别为2, 1
则有 (L + kC - N) = 2*(L + C - N)
即L = (k - 1)C + N
说明,如果我设定两个速度相同的指针,一个从起点开始遍历,一个从相遇点开始遍历,那么它们会在入口处碰撞
三.代码引入
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { if(head == NULL || head->next == NULL) return NULL; struct ListNode* fast, * slow; slow = fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* meet = fast; while(meet != head) { meet = meet->next; head = head->next; } return meet; } } return NULL; }
四.思路扩展
这道题如果将这个带还链表从相遇点断开,那么其实就是一个相交链表,交点就是环的入口
