一看就会的判断链表中是否有环求法

本文主要是介绍一看就会的判断链表中是否有环求法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断链表中是否有环

题目描述：

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度的解法么？
输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

示例：

输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true

题目链接：

判断链表中是否有环

思路1：

我们设置两个指针，一个slow指针（这个指针走得慢，一次走一个结点），一个fast指针（这个指针走的快，一次走两个结点），如果链表中有环，则fast指针肯定会追上slow指针。
根据上述思路，我们手写一下过程（根据例子）：
在这里插入图片描述
如果slow或者fast指针指向null就说明链中无环。
接下来我们实现一下代码吧。

代码1：

public class Solution {public boolean hasCycle(ListNode head) {if (head == null)return false;ListNode slow = head;ListNode fast = slow.next;while (slow.next != null && fast.next != null) {if (fast == slow) {return true;//两指针相遇，说明有环。}slow = slow.next;//slow指针一次走一个结点if (fast.next.next == null)//fast.next.next不为空才说明能走，不能走代表无环。return false;fast = fast.next.next;//fast指针一次走两步.}return false;}
}

思路2：

我们建议一个set集合，每遍历一个结点就判断set中是否存在该结点，有说明有环，没有的话，把该节点加入set中，直到遍历完该链表。

代码2：


import java.util.*;
public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<ListNode>();while (head != null) {if (set.contains(head))return true;set.add(head);head = head.next;}return false;}
}