An Algorithm every person who's learning Data Structures and Algorithms should know.
Introduction to Linked Lists:
Linked lists are one of the fundamental data structures used in computer science. A linked list consists of a sequence of nodes, each containing some data and a reference (or pointer) to the next node in the sequence. One of the most common problems encountered when working with linked lists is the need to traverse the list to find a specific node or to perform some operation on the nodes. One powerful technique that can be used to solve many of these problems is the "fast and slow pointer" method.
Fast & Slow pointer Method:
The fast and slow pointer method involves using two pointers that traverse the list at different rates. The "slow" pointer moves one node at a time, while the "fast" pointer moves two nodes at a time. This technique can be used to solve a variety of problems, including finding the middle node of a list, detecting a loop in a list, and reversing a list.
Types of problems solved using this method:
Finding the Middle Node of a List:
One problem that can be easily solved using the fast and slow pointer method is finding the middle node of a list. To do this, we simply initialize both the fast and slow pointers to point to the head of the list. We then move the slow pointer one node at a time and the fast pointer two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node.
Here is some sample code to find the middle node of a linked list using the fast and slow pointer method:
Node* slow = head;Node* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;Detecting a Loop in a List:
Another problem that can be solved using the fast and slow pointer method is detecting a loop in a list. This is done by initializing both pointers to the head of the list and moving them through the list at different rates. If the list contains a loop, the fast pointer will eventually catch up to the slow pointer, indicating the presence of a loop.
Here is some sample code to detect a loop in a linked list using the fast and slow pointer method:
Node* slow = head;Node* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {return true;}}return false;Reversing a List:
Finally, the fast and slow pointer method can also be used to reverse a linked list. This is done by initializing both pointers to the head of the list and then reversing the pointers as they move through the list. Specifically, the next pointer of the slow pointer is set to the previous node, and then the slow and fast pointers are moved one node at a time.
Here is some sample code to reverse a linked list using the fast and slow pointer method:
Node* prev = NULL;Node* slow = head;Node* fast = head;while (fast != NULL) {fast = fast->next;slow->next = prev;prev = slow;slow = fast;}return prev;
Conclusion:
In conclusion, the fast and slow pointer method is a powerful technique for solving a variety of problems related to linked lists. By using two pointers that traverse the list at different rates, we can easily find the middle node of a list, detect a loop in a list, and reverse a list. This method is efficient, easy to implement, and widely used in computer science. I learnt this method from Kunal Kushwaha today.
Special thanks to Kunal Kushwaha for being an amazing teacher.
Link to the video : https://youtu.be/70tx7KcMROc
Happy Learning
Feel free to message me on my Social accounts for any help.