怎样做 云知梦 网站seo经理招聘

题目：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解决方案一：

可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 空链表、单节点链表一定不会有环while (fast != null && fast.next != null) {fast = fast.next.next; // 快指针，一次移动两步slow = slow.next;      // 慢指针，一次移动一步if (fast == slow) {   // 快慢指针相遇，表明有环return true;}}return false; // 正常走到链表末尾，表明没有环}
}

解决方案二：

通过Set集合去重也能实现，效率不高图一乐

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

解决方案三：

提供一个全新的思路，一次遍历单指针搞定，时间击败100%。每次遍历完一个节点，将它的下一个节点指向初始节点，然后继续遍历： 如果下一节点为空，没有换 如果下一节点的下一指针为root，有环。

public class Solution {public boolean hasCycle(ListNode head) {ListNode root = head;while(head!=null){if(head.next==root) return true;//如果节点的下一节点为初始节点  有环ListNode tem = head; head = head.next;//否则继续遍历下一个节点tem.next = root;//上一个节点的下一节点为初始节点}return false;//走到了尽头，没有换}
}