Solution: Linked List Cycle
Tags: algorithms, javascript, leetcode
Published: 2021-02-03 18:41:20

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/linked-list-cycle/discuss/1048351/Javascript-or-Floyd's-Algorithm-Solution-w-Explanation-or-beats-96).*

---

####[Leetcode Problem #141 (*Easy*): Linked List Cycle](https://leetcode.com/problems/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 1 Visual](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

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 1 Visual](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)

Example 3:||
|---:|---|
*Input:*|head = [1], pos = -1
*Output:*|false
*Explanation:*|There is no cycle in the linked list.
*Visual:*|![Example 1 Visual](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
 
---

***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:**
```javascript
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
};
```