判断链表中是否有环
解法一：哈希法
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
HashSet<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head)){ //已存在说明遍历过，有环
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
解法二：快慢指针
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){ //相遇则说明有环
return true;
}
}
return false;
}
} 链表中的环的入口节点
解法一：哈希法
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
HashSet<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head)){ //已存在说明遍历过，有环
return head; //当前节点就为入环节点
}
set.add(head);
head = head.next;
}
return null;
}
} 解法二：快慢指针
思路
实现代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode h1 = head;
ListNode h2 = head;
while(h2 != null && h2.next != null){ //判断是否有环
h1 = h1.next;
h2 = h2.next.next;
if(h1 == h2){ //相遇则有环
h2 = head; //将h2重新指向头节点
while(h1 != h2){ //再次相遇的节点就是入环节点
h1 = h1.next;
h2 = h2.next;
}
return h1;
}
}
return null;
}
} 
