[LC Walkthrough] 141. Linked List Cycle
Hello world! This is the fourth article of LeetCode Walkthrough.
Today, I’ll be writing about 141. Linked List Cycle. It is the third question of February LeetCoding Challenge 2021.
For this problem, given a linked list, we need determine if it 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.
The main focus of the problem will be keeping track of nodes while we iterate over the list. You can use many data structures to achieve it, but the HashSet will be most efficient one out of them (since it guarantees constant time for insert and find).
We will traverse over the linked list and see if we face a node that we have seen before. If we do so, we will return true since it means there exists a cycle in the given linked list. If the loop successfully terminates, we will return false since it means there is no cycle.
With that in mind, we can come up with the following code:
Let us run a test case:
The time complexity of this solution is O(n) where n = # of nodes in the linked list. Whether there is a cycle or not, we will still fully iterate over the list.
The space complexity of this solution is O(n) where n = # of nodes in the linked list. We will be recording nodes we have seen on the HashSet, and it will grow to the size of n.
The popular follow-up to this question is to solve it using constant space. Funnily enough, I learned about this approach from Joma Tech’s video.
In short, we utilize Floyd’s tortoise and hare algorithm. It uses only two pointers, so we can achieve constant space usage with.
The algorithm’s basic idea is this: create two pointers which move through the linked list in different speed (e.g., one pointer will traverse by 1 node while the other pointer will traverse by 2 nodes). If there exists a cycle in the list, two pointers will meet at the same node at one point.
With that in mind, we can come up with the following code:
Let us run a test case on this code as well:
The time complexity of this solution is O(n) where n = # of nodes in the linked list. During the traverse, the slow pointer will have to fully traverse the list (n). Once both pointers enter the cycle, it will take approximately:
iterations for two pointers to be at the same node. The difference of speed is always going to be 1, and at worst case scenario, the distance between two pointers is going to be the length of the cycle which at max is going to be the length of the list (n). As a result, the overall time complexity will be O(2n), which can be simplified to O(n).
The space complexity of this solution is O(1), since we are only using two pointers.
Thanks for reading!
