This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #141 (Easy): Linked List Cycle
Description:
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Examples:
| Example 1: | |
|---|---|
| Input: | head = [3,2,0,-4], pos = 1 |
| Output: | true |
| Explanation: | There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). |
| Visual: |  |
| Example 2: | |
|---|---|
| Input: | head = [1,2], pos = 0 |
| Output: | true |
| Explanation: | There is a cycle in the linked list, where the tail connects to the 0th node. |
| Visual: |  |
| Example 3: | |
|---|---|
| Input: | head = [1], pos = -1 |
| Output: | false |
| Explanation: | There is no cycle in the linked list. |
| Visual: |  |
Constraints:
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked-list.
Idea:
One brute force solution here would be to map every single pointer in the list until we either reach the end of the list or find a duplicate, but that would use O(n) space.
The other brute force solution would involve counting nodes until we reached the designated constraint (10e4). If we pass that amount before reaching the end of the linked list, it must be a cycle. This solution is O(1) space, but much slower than an optimal solution.
But this problem is also an entry into the common question of cycle detection. One of the easiest methods of cycle detection is Floyd's Tortoise and the Hare algorithm, which states that if you define two branches (slow and fast), and have the slow branch perform a given function once per iteration and the fast branch perform the same function twice per iteration, that they will eventually meet at the same point if the function is cyclical.
In essence, we start the hare just ahead of the tortoise, let them go, and see if the hare cycles back around to catch up with the tortoise again.
Otherwise, if we ever reach the end of the linked list, we know that there can be no cycle.
Implementation:
For the javascript solution, we can also use optional chaining to good effect here to make the code slightly more readable.
Javascript Code:
var hasCycle = function(head) {
let slow = head, fast = head?.next
while (slow && fast)
if (slow === fast) return true
else slow = slow.next, fast = fast.next?.next
return false
};
Top comments (0)