Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
一个笨办法是将每个节点插入一个unordered_map里,每次插入前去查一下是否已经存在,这个方法需要额外的存储空间;另一个方法是用两个指针遍历链表,一个指针每次走一步,另一个指针每次走两步,如果有环,这两个指针必定会相遇,具体代码如下
1 | /** |
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
1 | /** |