Linked List Cycle: Swift

Hey folks, hope you all are doing well. Today I came up with another interesting leetcode problem. Let’s deep-dive into it.

Key Points:
- Understanding the problem statement
- What is a Linked List?
- Constraints.
- Approach.
- Conclusion.

Understanding the problem statement

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.

Certainly! The problem we’re trying to solve is to determine whether a given linked list contains a cycle. In a linked list, a cycle occurs when one of the nodes in the list has a reference (via the next pointer) to a node that was visited earlier in the list. This creates a loop or cycle in the linked list.

What is a linked list?
The linked list is implemented using a series of nodes, each containing a value and a reference to the next node in the sequence. The last node in the list typically has a next reference set to nil, indicating the end of the list.

(Linked List)

Constraints
Time Complexity: O(n)
Space Complexity: O(1)

Approach
There is a famous algorithm known as Floyd’s Tortoise and Hare algorithm, The algorithm ensures that the two pointers (tortoise and hare) move at different speeds through the linked list. If there’s a cycle, the hare will eventually catch up to the tortoise. This guarantees that the algorithm can detect cycles efficiently while traversing the linked list only once. We are going to solve this problem using this algorithm.

(Floyd’s Cycle Detection Algorithm)

There is a famous algorithm known as Floyd’s Tortoise and Hare algorithm. The algorithm ensures that the two pointers (tortoise and hare) move at different speeds through the linked list. If there’s a cycle, the hare will eventually catch up to the tortoise. This guarantees that the algorithm can detect cycles efficiently while traversing the linked list only once. We are going to solve this problem using this algorithm.

(Solution using Floyd’s algorithm)

• The hasCycle function takes the head of the linked list as an argument and returns a boolean indicating whether a cycle is present.
• Two pointers, slow and fast, are initialised to point to the head of the linked list. These pointers will help us traverse the list to detect a cycle.
• We use a while loop to iterate through the linked list. The loop continues as long as the fast pointer is not nil and the fast.next pointer is also not nil. This is because the fast pointer moves two steps at a time, so we need to ensure we can move both pointers without causing a null pointer exception.
• Inside the loop, the slow pointer moves one step ahead (slow = slow?.next) and the fast pointer moves two steps ahead (fast = fast?.next?.next). This creates a difference in speed between the two pointers.
• We check if slow and fast are pointing to the same node using the reference equality operator (===). If they are equal, it means the two pointers have met, which indicates a cycle in the linked list. In this case, we return true.
• If the while loop completes without detecting a cycle, it means there is no cycle in the linked list, so we return false.

Conclusion
The Floyd’s Tortoise and Hare algorithm is already quite optimized for cycle detection in a linked list. It achieves linear time complexity (O(n)) with constant space complexity (O(1)), which is the most optimal complexity you can achieve for this problem.

Further optimisation beyond the existing two-pointer approach would generally involve changing the fundamental algorithm, which could compromise its correctness or efficiency. Since the current algorithm is both correct and highly efficient, attempting to optimize it further could risk making the solution more complex and harder to understand without gaining significant benefits.

Until next time, see ya guys. Happy coding 👨🏻‍💻👩🏻‍💻