LeetCode Algorithm Challenges: Linked List Cycle
Question
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.
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).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.Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.What is Linked List?
To solve this issue it’s important to understand the data structure that it has. According to Wikipedia:
a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
So even though the linked list looks like an array head = [3,2,0,-4], we can’t refer to elements of the list as head[0].
Each node has 2 fields: val — represents value stored in the node, and next — which points to the next node.
Solution
How would we know if the linked list doesn’t have a cycle? Well, that should be simple, if the last node doesn’t have the next value. But if the last node points to a node within a list we have a loop/cycle. We can’t identify the last node in the list because lists don’t have length property like arrays.
But we can iterate through a list if at any point we reach a node without next pointer, it means there is no cycle. Assuming there is a cycle, we will use a method of going through the list at 2 speeds, at some point. If we have 2 runners, who are running in circles and one of them runs twice as fast as the other one, they will eventually meet. By looking at the image below we can see that at step 6 slower and faster tracks meet. So let’s code this out.
First, we will check if our list even exists, because if there is no list, there is no cycle.
if (!head) { return false;}
Now we will create 2 runners, fast_t and slow_t and each one will start at the same starting point.
let fast_t = head;let slow_t = head;
We need to check each element of the list therefore we will use a loop. Since we don’t know the length of the list it makes sense to use while loop. We will keep going until fast_t exists, keep in mind that our return statement will break the loop, so we won’t get stuck in an infinite loop.
while (fast_t) { ....}
The first step within the loop would be to check if the next exists, because if it doesn’t there is no cycle, and the problem is solved.
if (!fast_t.next) { return false;}
Otherwise, let's start our race and start moving our racers. So slow_t will move to the .next element of the list, but fast_t will move two elements forward (.next.next).
else { fast_t = fast_t.next.next; slow_t = slow_t.next;}
Now it’s time to check if they are at the same spot and if they are it means that they are running in circles and our list has a cycle, therefore we can return true.
if (fast_t === slow_t) { return true;}
It might seem like we’re done, but not just yet. There is an additional return statement that we need at the end of the function. What if fast_t doesn’t exist anymore and we break out of the loop. In that case, we know that there is no cycle and therefore we should return false.
return false;