Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
思路:
1. 首先考虑链表为空,链表为单节点以及双节点的特殊情况。
2. 不同速度的双指针(p1速度为1, p2速度为2)赛跑。
3. 赛跑的过程中如果发现快指针p2的next为空就一定没有环。
4. 如果存在环状结构,那么慢指针p1和快指针p2一定会相遇。
5. 如果快慢指针相遇,则一定存在环状结构。
Can you solve it without using extra space?
思路:
1. 首先考虑链表为空,链表为单节点以及双节点的特殊情况。
2. 不同速度的双指针(p1速度为1, p2速度为2)赛跑。
3. 赛跑的过程中如果发现快指针p2的next为空就一定没有环。
4. 如果存在环状结构,那么慢指针p1和快指针p2一定会相遇。
5. 如果快慢指针相遇,则一定存在环状结构。
No comments:
Post a Comment