The Slow & Fast Pointer approach is the second pattern that will come in handy when working on Linked list problems. We will learn this pattern by applying it to the following three problems:
Find Middle of Linked List
Find Kth-node from last
Detect a cycle in a Linked List
Middle of Linked List
As we know, we cannot directly access a Node at an index in Linked List, similar to how we do it in an Array.
Brute force technique: O(N + N/2)
First, find out the length of the linked list. This operation takes O(N) time if there are N nodes in the list.
Then, find out the Middle Node Index as (length_of_list/2). There are two scenarios, the list has either an odd or even number of nodes in the list.
Now you can easily move your pointer to the Middle Node Index.
While this is still overall O(N), we can do better than this to avoid some repetitive & unwanted work. Read ahead...
Optimized Solution: O(N)
This is where the Slow and Fast Pointers come in. Basically, the idea is to to move the two pointers at different rates. For example,
slow = slow + 1 => slow = slow.next (in Linked List terms)
fast = fast + 2 => fast = fast.next.next (in Linked List terms)
Both the pointers start at the head of the Linked List.
List 1 (Odd numbers of nodes): 1 -> 2 -> 3 -> 4 -> 5
List 2 (Even numbers of nodes): 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. Assuming that in case of even number of nodes in list there could be two possible middle nodes (3 & 4). We want to return the second one i.e 4.
Now, use your two index fingers one as Slow and one as Fast pointer on the above list and keep iterating as slow = slow.next and fast = fast.next.next. You will notice that when the fast pointer reaches the last node (in case of odd list) and the "null" (in case of even list), the slow pointer will be pointing to the middle fo the Linked list.
Code
Code to find the middle node of linked list
public Node middleNodeOfList(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
K-th Node from Last
The idea is quite similar to finding the middle of a linked list. The only thing that changes is the rate at which we move the slow and fast pointers.
Brute force Solution: O(N + (N-k))
Find the length of the Linked List. This is O(N) operation
To reach K-th node from last you need the pointer to move the pointer (N-K) times from the head.
This brings the overall time complexity to O(N + (N-k)).
But, we can do better than this. If you want to try it yourself, think about how to use the two pointers before reading the solution ahead.
Optimized Solution: O(N)
Take the following example, 1 -> 2 -> 3 -> 4 -> 5. And you need return 2nd node from the last i.e 4. Again for better visualization use your index fingers as pointers.
Start the Slow and Fast pointers at the Head initially.
Move the Fast pointer forward K-1 times. In our example, Fast pointer will be placed at Node 2.
Now, keep iterating slow and fast pointers until fast pointer reaches end of List. Like this, slow = slow + 1 and fast = fast + 1.
When Fast is at the last Node, Slow will be at the Kth Node from last. Similarly, in our example, when Fast is at 5, Slow will be at 4, which is the 2nd from the last in the list.
Code
public Node kthNodeFromLast(Node head) {
Node slow = head, fast = head;
while(k-- > 0) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
Detect a Cycle in a Linked List
This is a well-known problem that can be used with the Slow-Fast pointer approach. The idea behind detecting a cycle in a linked list is this:
you move the slow and fast pointer at this rate: slow = slow + 1 and fast = fast + 2, with each iteration i.e Fast pointer moves forward at twice the rate of the Slow pointer. Now at any point in time, if slow and fast pointers meet or point to the same node we can say a cycle was detected in the linked list.
Code
public boolean detectCycle(Node head) {
if (head == null) {
return false;
}
Node slow = head, fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
To Conclude...
The Slow & Fast pointer approach is yet another pattern to help you tackle Linked List problems. Although these questions are too simple to appear in an interview, the technique we learned in the above problems should fundamentally give you a way of approaching a variation or a twisted Linked List problem.
There are very limited things one could do with a Singly Linked List and I believe the Slow-Fast pointer approach pattern and the reversal pattern that we learned in our previous post on the linked list cover everything you need to know.
My goal is to teach you the patterns I have identified in all the different topics when I was preparing for my coding interviews. I hope that once you learn these, you feel confident enough to systematically think and try to apply the patterns you have learned to tackle any Leetcode easy, medium or hard problems.
