难度: 中等 标题：带环链表
给定一个链表，判断它是否有环。
思路
一开始想到的思路是放到hashmap里，每次前进一格就查询在hashmap中是否存在。存在则返回true，遇到null就返回false。但是这样需要额外空间。
后来的思路是两个指针first和second。second每次前进两格，first前进一格。若有环，second必定追上first。
思路想到后调试了很久，总是超出内存范围。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null){
return false;
}
ListNode first = head;
ListNode second = head;
while (first != null && second != null && second.next != null){
second = second.next.next;
first = first.next;
if (first == second){
return true;
}
}
return false;
}
}
|
链接
https://www.lintcode.com/zh-cn/problem/linked-list-cycle/
