141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
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?
---
Intuition
Brute force would be a visited set, and check against it if already visited, thats O(n) space
---
If there's a cycle, and two pointers are moving at different speeds, they will cross each other at some point - for eg., hands of a clock
Intuition
Brute force would be a visited set, and check against it if already visited, thats O(n) space
---
If there's a cycle, and two pointers are moving at different speeds, they will cross each other at some point - for eg., hands of a clock
Start two pointers at head, and move them 1 step, 2 step increments (as long as fast.next != null)
once they meet at some point, cycle is detected => return true
if fast pointer reaches null, there's no cycle => return false
---
Time - O(n + k) - n = non cyclic length, k = cyclic length
Space - O(1)
---
Related problems
find-duplicate-number
linked-list-cycle-ii
---
Time - O(n + k) - n = non cyclic length, k = cyclic length
Space - O(1)
---
Related problems
find-duplicate-number
linked-list-cycle-ii