Algorithm Gymnastics 21 LinkedList Cycle

LinkedList Cycle

Screen Shot 2020-08-04 at 23.00.15.png

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

Screen Shot 2020-08-04 at 23.19.07.png

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()

Recommended Posts

Algorithm Gymnastics 21 LinkedList Cycle
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List