JAVA练习293- 环形链表

题目概览给你一个链表的头节点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解释链表中没有环。提示链表中节点的数目范围是[0, 104]-105 Node.val 105pos为-1或者链表中的一个有效索引。进阶你能用O(1)即常量内存解决此问题吗来源141. 环形链表 - 力扣LeetCode解题分析方法一哈希集合用哈希集合存储遍历过的节点每次遍历判断即可。时间复杂度O(n)空间复杂度O(n)/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { SetListNode set new HashSet(); ListNode temp head; while(temp ! null) { if (set.contains(temp)) { return true; } set.add(temp); temp temp.next; } return false; } }方法二快慢指针定义指针 i 和 ji 遍历一个节点j 遍历两个节点如果存在环那么两个指针一定会有相遇的时候如果没有j 一定会先遍历完成。时间复杂度O(n)空间复杂度O(1)/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { ListNode a head, b head; while(a ! null b ! null b.next ! null) { a a.next; b b.next.next; if (a b) { return true; } } return false; } }