Template for Two Pointer in Linked List

 Steps :

1. First we need to initialize the slow pointer and fast pointer.

    // Initialize slow and fast pointers.
     ListNode slow = head;
     ListNode fast  = head;
   // Change the condition according to the problem.
  // Remember to avoid error prone.
    while(slow != null && fast !=null && fast.next!=null){
    slow = slow.next; // move slow pointer one step each time
    fast = fast.next.next; // move fast pointer two steps each time
    if(slow == fast){
    return true;
    }
    }
    return false;


Note :

1. Always make sure while  calling the next on the current node.
 
    Getting the next node of the null node will cause errors.

    So before we examine fast and fast.next make sure they are not null.

2. Carefully define the end conditions of the loop.

    Run several examples to make sure your end conditions will not result in error.


Complexity Analysis :

It is easy to analyze the space complexity. If you only use pointers the space complexity is O(1).

But the time complexity will change according to the problem.

In above scenario slow pointer moves one step each time and fast pointer moves two steps each time.

1. If there is no Cycle the fast pointer will move the end of the list in N/2 steps.

2. If there is a Cycle the fast pointer takes M times to catch the slow pointer where M is the length of the Cycle in the List.

Obviously M<=N , So we run the loop N times and it needs constant time . So the time complexity is O(N) in total.

Always try to calculate the worst case scenarios by taking different examples .