Fast and Slow Pointers

Question 1

141. Linked List Cycle

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

O(n)
O(1)

Answer 1

Takeaway:

1. Remember the while condition.
2. Re-initialization condition.
3. In the loop, slow and fast pointer equality must be checked after moving slow and faster pointers.

Pseudo code:

1. Declare two instance variable of ListNode named as slow, fast.
2. Initialize slow and fast both to head.
3. Iterate through while loop until fast is not null and fast.next is not null.
4. 1. Re-initialize fast with fast.next.next, slow with slow.next.
5. 2. If slow and fast are same return true.
6. In the last return false.