Given a linked list, return the node where the cycle begins. If there is no cycle, return
null.
Note: Do not modify the linked list.
思路:
1. 首先借用 Linked List Cycle 的结果判断链表是否存在环状结构。
2. 如果不存在返回为空。
3. 使用不同速度的双指针(p1速度为1, p2速度为2)赛跑,直到双指针相遇。
3. 从双指针相遇开始记录环状结构的长度,继续赛跑,直到下一次相遇。
4. 再次相遇时,可以确定慢指针p1从前一次相遇开始到现在走过的步数就是环状结构的长度。
5. 重置双指针,一个先走等同于环状结构长度的步数。一个停留在head。
6. 双指针以相同速度前进,直到它们相遇,此时节点就是环状结构的起始点。
1. 首先借用 Linked List Cycle 的结果判断链表是否存在环状结构。
2. 如果不存在返回为空。
3. 使用不同速度的双指针(p1速度为1, p2速度为2)赛跑,直到双指针相遇。
3. 从双指针相遇开始记录环状结构的长度,继续赛跑,直到下一次相遇。
4. 再次相遇时,可以确定慢指针p1从前一次相遇开始到现在走过的步数就是环状结构的长度。
5. 重置双指针,一个先走等同于环状结构长度的步数。一个停留在head。
6. 双指针以相同速度前进,直到它们相遇,此时节点就是环状结构的起始点。
No comments:
Post a Comment