Leetcode: Linked list cycle
Given the head of a linked list, determine if there is a cycle in the list. A cycle is defined as a chain of arbitrary length that point to the same node. As an added difficulty, the solution should have a space complexity of
The first observation is that the cycle can be of arbitrary length. Thus, saving the visited nodes in a set would have a space complexity of
O(n). Secondly, the numbers cannot be compared because numbers might be duplicated throughout the list. Instead, we need to compare the list objects themselves.
The solution involves using two pointers with different step sizes. The first pointer,
p1, has a step size of one and the second pointer,
p2, has a step size of two. Then iterate as long as either one of the pointers (
p2) reaches the end of the list or if both pointers point to the same object, in which case we found a loop.
Runtime: 112 ms, faster than 15.44% of Python3 online submissions for Linked List Cycle.
Memory Usage: 17.6 MB, less than 67.21% of Python3 online submissions for Linked List Cycle.