题目
给定一个链表，判断链表中是否有环。
如果链表中存在环，就返回true。否则，返回false。
方法一：哈希表
思路
这个方法就是遍历整个链表中的所有节点，每遍历一个节点就判断它此前是否被访问过
用哈希表来存储已经访问过的节点，之后每到达一个节点时，如果该节点已经在哈希表里，就说明这个链表中有环
否则就把这个节点存入进去，重复这么一个过程，直到整个链表被遍历完
代码实现
import java.util.*;
public class test {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node3);
Solution solution = new Solution();
System.out.print("" + solution.cycle(head));
}
}
class Solution{
public boolean cycle(Node head) {
Set<Node> seen = new HashSet<Node>();
while (head != null){
if(!seen.add(head)){
return true;
}
head = head.getNext();
}
return false;
}
}
class Node{
private int Data;
private Node next;
public Node(int Data){
this.Data = Data;
}
public int getData(){
return Data;
}
public void setData(int Data){
this.Data = Data;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
|
这里用到了HashSet，HashSet是基于Hashmap来实现的，是一个不允许有重复元素的集合
添加元素用add()方法
算法主体
class Solution{
public boolean cycle(Node head) {
Set<Node> seen = new HashSet<Node>();
while (head != null){
if(!seen.add(head)){
return true;
}
head = head.getNext();
}
return false;
}
}
|
复杂度
时间复杂度：O(N)，N是链表的节点数。最坏情况需要把链表中每一个节点遍历一次。
空间复杂度：O(N)，N是链表的节点数。主要是为哈希表的开销，最坏情况需要把每个节点插入到哈希表中一次。
思考：能不能用O(1)的空间复杂度来解决这个问题。
方法二：快慢指针
思路
这个方法称为Floyd判圈算法(又称为龟兔赛跑算法)
在开始的时候给定两个指针，一个快，一个慢
如果链表中存在环，那么快指针会在某一时刻追上慢指针，即二者相等，而快指针已经套了慢指针几圈了
如果链表不存在环，那么快指针就会先入空或指向空
这样循环条件都得到了
注意：因为判断是否追上的条件是fast == slow，所以slow一开始在head节点，那么fast就要在下一个节点，以防二者一开始就相等破坏循环条件。
代码实现
public class test {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node3);
Solution solution = new Solution();
System.out.print("" + solution.cycle(head));
}
}
class Solution{
public boolean cycle(Node head) {
if(head == null || head.getNext() == null){
return false;
}
Node slow = head;
Node fast = head.getNext();
while (slow != fast){
if (fast == null || fast.getNext() == null){
return false;
}
slow = slow.getNext();
fast = fast.getNext().getNext();
}
return true;
}
}
class Node{
private int Data;
private Node next;
public Node(int Data){
this.Data = Data;
}
public int getData(){
return Data;
}
public void setData(int Data){
this.Data = Data;
}
public Node getNext(){
return next;
}
public void setNext(Node next){
this.next = next;
}
}
|
算法主体
Java
class Solution{
public boolean cycle(Node head) {
if(head == null || head.getNext() == null){
return false;
}
Node slow = head;
Node fast = head.getNext();
while (slow != fast){
if (fast == null || fast.getNext() == null){
return false;
}
slow = slow.getNext();
fast = fast.getNext().getNext();
}
return true;
}
}
|
C
bool hasCycle(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return false;
}
struct ListNode* slow = head;
struct ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
|
复杂度
时间复杂度：O(N)，其中 N 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
空间复杂度：O(1)。只使用了两个指针的额外空间。
