描述
给定一个链表，判断它是否有环。
样例
给出 -21->10->4->5, tail connects to node index 1，返回 true
挑战
不要使用额外的空间
思路
- 使用O(n)的额外空间时，在遍历整个链表的过程中用一个hash表存储当前结点的引用，如果hash表中已经存在当前结点的引用return false，否则加入hash表，如果遍历完整个链表仍旧没发现重复值证明链表没环
- 定义两个指针，一个快一个慢，设定快的跑两步，慢的跑一步，如果有环则它们一定会相遇
两种思路时间复杂度都是O(n)
变形题目
题目有一种变体，就是判断两个链表有没有交集，将第一个链表的末指针和第二个链表的头指针连接到一起，若有交集则一定存在环
代码
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
- 哈希表法
public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
}
- 快慢指针
public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
// 注意要让跑的快的在前面，不然没跑完一圈就追上了
ListNode slow = head;
// 如果 fast 也赋值为 head 则在第一个结点就会跳出 while 循环
ListNode fast = head.next;
while (slow != fast) {
// 在没追上慢指针的情况下，遍历完了整个链表，证明没有环
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
// slow == fast时证明有环
return true;
}
}
