Reverse Linked List

Each element of the linked list consists of two parameters i.e. the value of the element and the address of the next element in the linked list. When we talk about reversing the linked list, we mainly focus on manipulating the address of the next linked list for each element. 

If we observe the above figure while reversing the linked list, we didn't reverse the value of each element rather we reversed the address of the next element of each element in the linked list. 

To execute this, we can make use of three pointers, the main pointer will iterate throughout the linked list, and the other two pointers will help in reversing the address of the next element in the linked list. Let's have a look at the below logic to reverse the linked list:

1 2 3 4 5 6 7 8 9 10 11

ListElement main = head; ListElement prev = null; ListElement next = null; while (main != null) {     next = main.next; main.next = prev; prev = main; main = next; } head = prev; return head;

In the above logic, ListElement is the object for an element of the linked list which contains the value and the address of the next element. We will start by declaring three pointers, i.e. main, prev, and next.

Next, the while loop will help us to iterate through the list, let us have a look at the first iteration:

If we observe here, at step 3 of the iteration, the linkage between the first and second element became null and the prev pointer is pointing to the first element so that we can point back the second element to the first element in the second iteration and reverse the first two elements.  Let's have a look at the second iteration:

            

Again after the second iteration, the second element is pointing to the first element of the linked list, and the first two elements are reversed at Step 2. Also, while the second element starts pointing to the first element, the linkage between the second element and the third element became null and is set to reverse in the third iteration. Let's have a look at the third iteration:

            

After the third iteration, the second and third elements are reversed and the last element is pointing to null. This will eventually point to the third element in the fourth iteration with the help of the prev pointer. Let us have a look at the fourth iteration:

                

Eventually, after the fourth iteration, all the elements will point in the reverse direction and the next and main pointers will become null. Since the main pointer becomes null, the iterations will stop. The only thing left is to point the head correctly. Since the linked list is reversed, the head should point to the last element of the original linked list. This can be achieved with the help of the prev pointer again. We can simply assign head = prev after the iterations are completed and return the new head of the reversed link list.

The above logic will help in reversing the linked list.

Read More

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

Two Pointers

Two Pointers is a technique of solving problems of linear data structure, especially arrays. It helps to solve problems with lesser time complexity and space complexity and simplifies our code. Let us have a look at a few of the basic problems solved using two-pointers to understand the concept better. Ideally, we point to the first and last index of an array or the first and second index of an array to iterate the array and then move the pointers accordingly. The approach followed in the below problems might help us in solving more complex problems with an easier approach.

TO FIND A SORTED ARRAY OF SQUARES OF A SORTED ARRAY

Let us assume that we need to figure out an array of squares of a sorted array in increasing order. For Example, we need to find a sorted array in increasing order for squares of the element of [-5,-3,-1,0,3,4,6]. 

One way to achieve this is to iterate every member of the given array, square it and store it in a result array. Next, we can sort the result array. If we follow this approach, the time complexity will include the time to iterate the array and the time to sort it. 

Two pointers can help us in this case to minimize the time complexity. Let's declare two integers to point to the first and last index of an array as shown in the below figure. We can then declare a result array and iterate it from last to end and for each iteration of the result array; we can check the square of the start and end pointer. Whichever, square value is greater can be filled in the result array and the pointer can be decreased if it was the end pointer or can be increased if it was the start pointer. This will help us in getting the desired result.

In the above figure, the pointers are placed at -5 and 6 and an empty result array is declared. Next, the square value of both the pointers is computed and it is determined that 36 Is bigger than 25. Hence, 36 is stored in the result array and the end pointer is decreased by 1. 

In the next step, we computed the square value of both the pointers again and determined that 25 is bigger than 16. Hence, 16 is placed in the result array and the start pointer is incremented by 1. 

Once we are done iterating all the elements of the result array, we will get the desired sorted result.

TO MOVE ALL THE ENTRIES OF A PARTICULAR VALUE AT THE END OF THE ARRAY

Next, we will try to move all the entries of a particular value to the end of the array. Let us try to move all the "1" from the array [1,1,0,3,2,8,1]. 

An easier way to solve this problem is to create a new array of the same size and insert all the non "1" entries from the original array to the new array by iterating the original array. Once the iteration is completed, we can add 1 to the remaining indexes of the new array to get the desired output.

An efficient way to solve this problem is via the two-pointers approach. Let us have a look at the diagram below to understand the execution flow:

To solve this problem, we can initiate two pointers at the start of the array only, and can execute a loop until the second pointer is less than the size of the array and follow the below logic:

• If the second pointer value is "1", increment the second pointer and continue the loop.
• If the second pointer value is not "1", check the first pointer value and second pointer value. If they are not the same, swap the values.
• Increment both first and second pointer.

This approach will help us save some space complexity as no new array creation will be required and is an efficient way to solve the problem.

HOW TO REVERSE A STRING USING TWO POINTERS

Let's try to reverse a string. The string is nothing but an array of char, we can apply the two-pointers approach to simplify the problem. Let's assume that we have been given a char array ['A','U','T','O','P','A','C','E'] and we need to get reverse the array and obtain ['E','C','A','P','O','T','U','A'].

Let us declare a start pointer and an end pointer in this case. We can run a loop until the start pointer is less than the end pointer and can follow the below logic:

• Swap the start pointer and end pointer values.
• Increase the start pointer by 1 and decrease the end pointer by 1.

The below diagram shows the complete execution for this problem:

The two pointers can be extended to be used as a fast-slow pointer which is explained in detail in our blog Fast-Slow Pointers.

Read More