题目：判断循环链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环
import java.util.ArrayList;
import java.util.List;
/**
* @author cosefy
* @date 2020/6/9
*/
//创建结点类
class ListNode {
int val;
ListNode next;
//构造函数
ListNode(int x) {
val = x;
next = null;
}
//添加结点的方法，返回的结点是添加后的结点
public ListNode add(ListNode node) {
this.next = node;
return node;
}
}
//主类
public class HasCycle {
public static void main(String[] args) {
List
list.add(1);
list.add(2);
int pos = 1;
ListNode head = getLinkedList(list, pos); //调用创建链表方法
boolean b = hasCycle_Test1(head); //调用判断链表是否循环的方法
System.out.println(b);
}
解法一：双指针法：
**思路**：利用快慢指针，每次慢指针向后移动一次，快指针移动两次，若链表为循环链表，则快慢指针有相等的情况；若链表不为循环链表
则快指针会指向null。
**分析**： 时间复杂度为O（n），运行效率很高
**易错点**：注意空指针异常的情况，不要直接移动快指针两次，移动之前要判断是否为空。
public static boolean hasCycle_Test1(ListNode head) {
if(head==null)
return false;
ListNode slow_node = head;
ListNode fast_node = head;
while(true){
if(fast_node.next==null )
return false;
if(fast_node.next.next!=null){
slow_node=slow_node.next;
fast_node=fast_node.next.next;
}else{
return false;
}
if(fast_node==slow_node)
return true;
}
}
//解法二：哈希表
/*
思路：粗放结点到哈希表中，若结点尾部为空，说明不循环，若遍历的当前结点和哈希表的存的已有结点相同，则说明循环。
分析：时间和空间复杂度都为O（n）
代码不再单独写出
*/
根据列表创建链表，并返回首结点：
public static ListNode getLinkedList(List
if(pos+1>list.size()) {
System.out.println("结点个数"+ list.size()+" 插入结点位置： "+pos);
throw new IllegalArgumentException("非法参数异常");
}
if (list.size() == 0)
return null;
ListNode first = new ListNode(list.get(0));
ListNode cur = first;
for (int i = 0; i < list.size(); i++) {
if (i == 0)
continue;
cur = cur.add(new ListNode(list.get(i))); //添加结点
}
if (pos != -1)
cur.next = getLinkedNode(first, pos); //将尾结点指向指定位置的结点
return first;
}
函数返回指定位置的结点：
public static ListNode getLinkedNode(ListNode head, int pos) {
int i = 0;
while (i < pos) {
i++;
head = head.next;
}
return head;
// throw new IllegalArgumentException("非法参数异常");
}
}