来自Leetcode第141题环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
丑陋的双指针
用一个快指针，一个慢指针，快指针每次比慢指针多走1步，这样，如果有环的话两者迟早相遇。
但是写的时候循环条件选择不当，导致出现了3次空指针异常，最终加了几个if判断才过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public boolean hasCycle(ListNode head) {
if(head == null || head.next == null)
return false;
ListNode p1 = head,p2 = head;
while (p1 != null && p2 != null){
p1 = p1.next;
if(p1 == null || p2.next == null)
return false;
p2 = p2.next.next;
if (p2 == null)
return false;
if(p1.val == p2.val) {
return true;
}
}
return false;
}
|
哈希表
通过向哈希表里添加结点，每次询问是否包含此节点来判断是否成环.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public boolean hasCycle(ListNode head) {
if(head == null || head.next == null)
return false;
Set<ListNode> map = new HashSet<>();
while(head !=null){
if(map.contains(head))
return true;
else{
map.add(head);
}
head = head.next;
}
return false;
}
|
双指针
来自题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
|