Fast and Slow Pointer

We can extend two pointers approach and use them as fast and slow pointer as well to solve more complex problems. In slow and fast pointer, we mostly extend slow pointer by 1 index and fast pointer by 2 indexes. This algorithm is known as Floyd’s Cycle Detection Algorithm. Let us look at a few of the solutions to better understand this algorithm.

TO CHECK IF THE TAIL OF THE LINKED LIST IS POINTING BACK TO ANY ELEMENT IN THE LINKED LIST

The fast-slow pointer can help us figure out if the tail of the linked list is pointing to any of the elements in the linked list. We will assign both the slow and fast pointers to the head of the linked list and will increment the slow pointer by 1 and the fast pointer by 2 in every iteration. If the fast pointer matches the slow pointer, that means the fast pointer re-iterated and the tail is not pointing to null. In case the tail is pointing to null and since the fast pointer was getting increase by 2 and the slow pointer was getting increased by 1. The fast and slow pointer should never point to the same element in the linked lsit.

TO FIND THE MIDDLE ELEMENT OF THE LINKED LIST

We can make use of this algorithm to find the middle element of the linked list quickly. We can start by pointer both of our pointer to the head of the linked list and we will move the slow pointer by 1 index and fast pointer by 2 indexes. We need to continue this until the fast pointer points to null or the linked list's last element. We can understand this flow with the help of the below diagram:

If we will observe the flow, by the time the fast pointer reaches the end (in case an odd number of elements are present in the linked list) or points to null (in case of even number of elements are present in the linked list), the slow pointer reached the middle element.

TO CHECK IF THE LINKED LIST IS PALINDROME

We can make use of the fast-slow pointer to check if the linked list is palindrome or not. We can follow the below flow to check the palindrome:

1. Make use of a fast-slow pointer to iterate the slow pointer until the linked list's middle element.

2. While iterating, the slow pointer till the middle element, we will be reversing the linked list.

3. Once the linked list is reversed, we will be having two different links linked list just need to place our pointers again to the head of both the pointers and compare if the elements are equal or not. If they are equal, then it is a palindrome.

Two reverse a linked list, we need to use 3 pointers, which is discussed in detail in our blog Reverse Linked List. Since we need to reverse only half of the linked list, we will be adding one additional pointer to figure out the middle element. Hence, in this case, we will be using four-pointers. Two of them will be used to figure out the middle element and the other two will be used to reverse the linked list:

Next, we will be assigning the slow and fast pointer to the head of the linked list and previous and next pointers as null for start. Next, we will follow the below logic until we iterate till the middle of the linked list to iterate the first half of the linked list:

1 2 3 4 5 6 7 8 9

while(fast != null && fast.next != null){ fast = fast.next.next; next = slow.next; slow.next = previous; previous = slow; slow = next; }

Let us say that the linked list is 1->2->2->1, after the first iteration of the while loop:
- The fast pointer will be at the 3rd element of the linked list.  (Image 2)

- The next pointer will be at the 2nd element of the linked list. (Image 3)

- The slow.next will become null i.e. the first element will stop pointing to the second element. This is required as we need to reverse the point which will be completed in the second iteration of the loop. (Image 4)

- The previous pointer will be at the 1st element of the linked list. (Image 5)

- The slow pointer will be at the second element, the same as the next pointer. (Image 6)

After the second iteration is completed, we will reach out middle element and the first half of the linked list will be reversed.

Post the second iteration of the while loop:
- The fast pointer will be null, making sure it will be the last iteration. (Image 1)

- The next pointer will move to the 3rd element. (Image 2)

- The slow.next will point to the previous pointer element i.e. the first element in this case. At this step, the linking is reversed. (Image 3)

- The previous pointer will then move to the second element. (Image 4)

- The slow pointer will move to the 3rd element of the linked list (Image 5)

This will help us divide the linked list into two separate linked lists. Next, we need to get two pointers to point to the head of these separate linked lists.

1 2 3 4 5 6 7 8 9

//Initiating Fast pointer to second linked list head. if(fast == null){ fast = slow; } else { fast = slow.next; } //Initiating Slow pointer to first linked list head. slow = previous;

The above logic will help us to get the head of both the linked list. For the second linked list, we need to check if fast is null or not.
If the fast pointer is null, we can assign the slow pointer reference to the fast pointer directly as it will be the case of even elements in the complete linked list. Hence, the slow pointer will be referring to (number of elements/2 -1).  
In case fast is not null, it explains that the fast pointer is referring to the last element of the linked list which means that the number of elements in the linked list is odd and in this case, the slow pointer is exactly pointing to the middle element. Hence, we can assign slow.next to fast pointer as we need not check the middle element for palindrome in case of odd elements linked list.

Once we have the separate linked list, we can simply iterate it using the below logic and checking each value. If any of the values are incorrect, the linked list is not a palindrome.

1 2 3 4 5 6 7 8 9

while(slow != null && fast != null){ if(slow.val != fast.val){ return false; } slow = slow.next; fast = fast.next; } return true;

Read More