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.