image.png
//hashtable
//Time complexity O(n)
//Space complexityO(n)
// public boolean hasCycle(ListNode head) {
// Set<ListNode> nodes = new HashSet<>();
// while (head != null) {
// if (nodes.contains(head)) {
// return true;
// } else {
// nodes.add(head);
// }
// head = head.next;
// }
// return false;
// }
/**
* Time complexity O(n)
* Space complexityO(1)
* @param head
* @return
*/
public boolean hasCycle(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;
}
}
网友评论