LeetCode #141: Linked List Cycle

LeetCode Solutions

https://leetcode.com/problems/linked-list-cycle/description/

To solve this problem, we can use the two-pointer technique. We will have two pointers, a slow pointer and a fast pointer. The slow pointer will move one step at a time while the fast pointer will move two steps at a time. If the linked list contains a cycle, the fast pointer will eventually catch up to the slow pointer.

Algorithm:

  1. Initialize slow and fast pointers to the head of the linked list.
  2. Traverse the linked list using the slow and fast pointers.
  3. If the fast pointer is null, return false as there is no cycle in the linked list.
  4. If the fast pointer and slow pointer meet at any point during traversal, return true as there is a cycle in the linked list.
  5. Return false if the traversal completes without any cycle.

Let’s implement the above algorithm in Python.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        
        return False

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. In the worst case, we would need to traverse the entire linked list to determine whether there is a cycle or not.

The space complexity of this algorithm is O(1), as we only need two pointers to keep track of the nodes in the linked list. This means that the amount of additional space used by the algorithm does not increase with the size of the input, making it an efficient solution for large linked lists.