Linked List Patterns
In this article let’s see one of the important patterns in the linked list data structure.
Before that let’s learn why we are going for a linked list over an array. Since arrays are naturally non-dynamic in nature we cannot add elements beyond the limit. For example if you declare an array with size of 10 like nums[10] you can only have at most 10 elements you cannot add beyond that limit.
Pros:
Deletion of elements in an array is costly compared to the deletion of elements in the linked list. Because, if you delete an element in an array, you have to shift every element which makes it complicated whereas in the linked list just manipulating the pointers is enough.
Cons:
The con is that searching of element takes more time(Worst case is O(n)) .
Example : For searching the 2nd element in the linked list we have we traverse 2 time(nth element requires n traversal), but in the case of array it takes only constant time O(1).
Types:
There are several kinds of linked list are there like singly linked, doubly linked list and circular linked list.
But most of the interview problems use a singly linked list.
Approaches:
Mostly the interview problems rounds around the following approaches,
Two pointers
Merge linked list
Dummy node
Reverse linked list
These 4 logic or concepts are easy to learn and we can collage these logic together which make things easier which seemed to be tough. In this article, let’s learn what is slow and fast pointers.
What is two pointer?
As the name suggest, we have to solve certain problem with the help of two pointer. The famous two pointer is the use of fast and slow pointer(this algorithm is also known as Floyd’s Algorithm) ,if the slow pointer moves 1 step ahead, then the fast pointer moves 2 step ahead.
Where to Use?
👊when you asked to find the middle node.(Slow and Fast pointers).
👊When you asked to merge two sorted lists.
👊When you asked to detect cycle in the linked list.
👊When you are asked to check palindrome(You have to use the concept of reversing too).
👊When you are asked to remove the duplicate elements in linked list.
How to use:
Let’s see how to use fast and slow pointer :
876.Finding the middle node in linked list[EASY]
The problem statement goes like,
Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.
Sample Test Cases:
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.What they asked us to is to find the middle node return that middle node and now that will act as head.
How to do is that simply use two pointers (Slow and fast pointer).
Initially assign both slow and fast pointer to the head address. Move fast pointer twice as the slow pointer. Here, in our problem we have to move fast pointer 2 steps and slow pointer 1 step until the fast and next of the fast pointers become null. At the end of the traversal the slow pointer will points to the middle element.
Let’s dry run this approach for this problem.
Consider the numbers I used in the below is all about their address.
Initially fast = slow = head (i.e it points to the 1st element in the example 1 it is 1). fast=1 and slow=1.
1st iteration: slow= 2 and fast =3
fast!=null and fast.next!=null so continue the iteration
2nd iteration: slow=3 and fast=5
Now fast!=null and fast.next=null so break the iteration and return the slow pointer. In this case the slow pointer is the address that points to the 3.
This is the thought process behind this problem.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
Try the above program and get to understand about the flow using the debug pointers.
Let’s solve another problem where we use this approach which is a famous and frequently asked problem in big tech companies in my next article.
If you find any value in this article, consider FOLLOWING me! Thanks 😇
#LearnInPublic #HappyCoding
