Leecode之环形链表进阶

一.题目及剖析

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; } 四.思路扩展

这道题如果将这个带还链表从相遇点断开,那么其实就是一个相交链表,交点就是环的入口