Instructions
Describe a function that can detect the presence of loops in a Linked List. Rather than writing an actual function, describe the strategy you would employ.
Input: Linked List
Output: Boolean
Hints
• From JS Data Structures: Linked List (https://codeburst.io/js-data- structures-linked-list-3ed4d63e6571):
A Linked List is an ordered, linear structure, similar to an array. Instead of items being placed at indices, however, they are connected through a chain of references, with each item containing a reference to the next item.
Solution1
How it Works
We can keep track of every single node we come across by throwing it into an object. As we go through each node in the linked list, we check our object for its presence. If present, we know we’ve come across it before, indicating a circular list.
Time
The time complexity of this would be: O(n)
Space
The space complexity is also:
O(n),
as we have to store potentially every value in the list.
Challenge
Make this function have O(1) space complexity.
Solution 2
How it Works
We create two counters which both start at the beginning of the list. They advance forward. The first advances one node at a time and the second advances two nodes at a time.
If there is a null node anywhere, signifying the end of the list, we can return false . Otherwise, the two counters will eventually fall on the same node. If the fast and slow pointer ever converge, this verifies a circle in the list, allowing us to return true.
Time
The time complexity is:
O(n).
If the list isn’t circular, we simply wait for the fast pointer to get to the end. It
has to traverse half the nodes, sD time complexity is o(n)
If the list is circular, the slow and fast pointer will always find each other by
the time the slow pointer has reached the end of the list.
Space
0(1),
since we don’t store any of the nodes.
Top comments (0)