[PYTHON] Algorithm Gymnastics 21 LinkedList Cycle

LinkedList Cycle

As shown in the image above, write a function that determines if the LinkedList is a cycle.

Solution Use slow and fast pointers to traverse the LinkedList. At each iteration, the slow pointer moves one step and the fast pointer moves two steps.

If there is no cycle, you will get two results.

1. If the LinkedList has no cycles, the fast pointer reaches the end of the LinkedList before the slow pointer, indicating that the LinkedList has no cycles.
2. If the LinkedList has no cycles, the slow pointer cannot catch up with the fast pointer.

If the LinkedList has cycles, the fast pointer goes into the cycle first, followed by the slow pointer. After this, both pointers continue to move indefinitely in the cycle. If you meet both of these pointers at any stage, you can conclude that the Linked List has a cycle. Let's analyze if the two pointers can meet. There are two possibilities when the fast pointer approaches the slow pointer from behind.

1. The fast pointer is located one behind the slow pointer.
2. The fast pointer is located two behind the slow pointer.

All other distances between the fast and slow pointers result in one of these two possibilities. Let's analyze these scenarios, considering that the fast pointer always moves first.

1. If the fast pointer is one step behind the slow pointer: the fast pointer moves two steps, the slow pointer moves one step, and both meet.
2. If the fast pointer is two steps behind the slow pointer: the fast pointer moves two steps and the slow pointer moves one step. After the move, the fast pointer is one behind the slow pointer, and this scenario results in the first scenario.

demo

Implementation

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next

def has_cycle(head):
  # time complexity O(n)
  # space complexity O(1)
  fast, slow = head, head
  while fast is not None and slow is not None:
    fast = fast.next.next
    slow = slow.next
    if fast == slow:
      return True
  return False


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))


main()