141 — Linked List Cycle
Restating Info We’re Already Given:
- We have to return a boolean indicating whether the passed in linked list contains a cycle.
- We are given the head of the linked list and have to traverse it using next.
- Internally, pos tells us if there’s a cycle but we can’t use it in our implementation.
- There is a possibility of there being no nodes.
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- N/A
Discuss Naive Solution:
Naively, we could use a set to store already seen nodes’ memory addresses. Every node is an object, and each unique node has its own memory address. Then, as we traverse the linked list, we check every node to see if we’ve seen that memory address before. If so, there’s a cycle.
Note: To get the memory address of a Python object o, use: id(o).
Discuss Optimal Solution:
Ideally, we’d use constant space not linear space. To do this, we can use Floyd’s cycle-finding algorithm. This algorithm uses 2 pointers that move at different speeds. Assuming there is a cycle, at one point the 2 pointers will have to point to the same object (in this case, LinkedList node) as they move at different speeds.
Code Optimal Solution:
Runtime/Space Complexity:
The runtime complexity of this algorithm is linear as it either fast or fast.next hits the end of the LinkedList and we return False or point to the same node and we return True. The space complexity of this algorithm is constant as we only need 2 pointers.
Test Cases:
- Empty linked list
- Linked list with no cycle
- Linked list with cycle of odd length
- Linked list with cycle of even length
