Wednesday, October 21, 2015

Linked List Cycle II

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. 双指针以相同速度前进,直到它们相遇,此时节点就是环状结构的起始点。

No comments:

Post a Comment