Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node. Example 2: Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node. Example 3: Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list. Follow up: Can you solve it using O(1) (i.e. constant) memory?
/** * 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) { if(head == null) return false; Set<ListNode> set = new HashSet<>(); ListNode current = head; while(current != null) { if(set.contains(current)) return true; set.add(current); current = current.next; } return false; } }/** * 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) { // If there is no node or just one node in the linked list if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } }/** * 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) { if(head == null) return false; ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if(slow == fast) return true; } return false; } }