141. Linked List Cycle
Easy
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?
package leetcode.easy;
/**
* Definition for singly-linked list. class ListNode { int val; ListNode next;
* ListNode(int x) { val = x; next = null; } }
*/
public class LinkedListCycle {
public boolean hasCycle1(ListNode head) {
java.util.Set<ListNode> nodesSeen = new java.util.HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
public boolean hasCycle2(ListNode head) {
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;
}
@org.junit.Test
public void test1() {
ListNode ln1 = new ListNode(3);
ListNode ln2 = new ListNode(2);
ListNode ln3 = new ListNode(0);
ListNode ln4 = new ListNode(-4);
ln1.next = ln2;
ln2.next = ln3;
ln3.next = ln4;
ln4.next = ln2;
System.out.println(hasCycle1(ln1));
System.out.println(hasCycle2(ln1));
}
@org.junit.Test
public void test2() {
ListNode ln1 = new ListNode(1);
ListNode ln2 = new ListNode(2);
ln1.next = ln2;
ln2.next = ln1;
System.out.println(hasCycle1(ln1));
System.out.println(hasCycle2(ln1));
}
@org.junit.Test
public void test3() {
ListNode ln1 = new ListNode(1);
ln1.next = null;
System.out.println(hasCycle1(ln1));
System.out.println(hasCycle2(ln1));
}
}