LeetCode 141 题目 环型链表
给定一个链表，判断链表中是否有环
解决方案
哈希表
顺着链表遍历每一个节点，判断之前是否访问过该节点，如果访问过，则判定为含有环，如果没有访问过并且到达了链表尾部(对象为null)，则没有环,每次访问过后节点地址存在SET中。
/**
* 方法1
*
* 思路
* 遍历每一个节点，判断之前知否曾经访问过，访问过则有环，没有访问过且当前为NULL，则没有环
*
* 时间复杂度 O(n)
*
* @param head
* @return
*/
public boolean hasCycle(ListNode head){
Set<ListNode> set = new HashSet<>();
for(;;){
if(head == null){
return false;
}
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
}
快慢指针
两个指针，起初都指向头指针，第一个指针每次往后移动1格，称它为慢指针，第二个指针每次往后移动2格，称它为快指针，如果没有环，则快指针率先到达尾部(对象为null),如果有环，则快慢指针会依次进入环中并在某个时刻指向同一个对象。
/**
* 方法2
*
* 思路：
* 快慢指针，快指针每次前进2格，慢指针每次前进1格，如果遇到NULL，则表示达到链表尾部，没有环，如果快指针和慢指针相等，则有环
*
* @param head
* @return
*/
public boolean hasCycle(ListNode head) {
if(head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
for(;;) {
fast = fast.next;
if (fast == null) {
return false;
}
slow = slow.next;
if (slow == null) {
return false;
}
slow = slow.next;
if(slow == null){
return false;
}
if (slow == fast) {
return true;
}
}
}
