Code - Linked List - Reverse A Linked List Singly/Doubly
PROBLEM: Given a head or the starting point of a singly linked list, reverse the linked list
UNDERSTANDING:
So before going for the implementation we would have to understand what a linked list is and how does it work. Linked List is a data structure, a linear data structure to be more precise which has a value and also an address/pointer to the next element in the list. In case of doubly linked list, along with value and the pointer to the next element. it will also store information about previous element. A small visual representation for the same below
And when we say it points to the next element or previous element, its actually pointing to the memory address where next and/or previous element is placed. More about linked list in below article. Feel free to go over it as understanding the functioning and structure if linked list is important to solve linked list related questions.
As we have got the understanding of the data structure. Let's understand the problem / code at hand. One can directly jump at the implementation part if one has the gist of the same.
REVERSE:
Whenever we say reverse a number or reverse a string, we generally think of it like the first element, or first character should be at last position and one at the last position would be at the first position. Right?
There is also another way to look at it. And this involves understanding from the perspective of each position.
Let's take an example to understand this better. Suppose we have a number 1234 which we want to reverse.
Let's separate the digits out and make each digit as a person. So, we would have
Person1 > Person2 > Person3 > Person4
Also, the reverse would be,
Person4 > Person3 > Person2 > Person1
Let's talk from Person2 perspective. Person2 would say in the reversed list, my previous person in the original list would be my next person
Person2 > Person1
and my next person in the original list would be my previous person.
Person 3 > Person2
Basically, every element would say,
My Previous Is My Next And My Next Is My Previous (Iterative Approach)
However, if we take Person1's perspective here, we can also say this as
I Will Be My Next Element's Next Element (Recursive Approach)
We would be approaching the solutioning with the same logic. The first one being an iterative approach while the latter being an recursive one.
IMPLEMENTATION:
As discussed above, we understood that we would need information about the previous and next element for this. From implementation perspective this can be done either with an iterative manner or by following a recursive approach. We will have a look at both here.
ITERATIVE:
public static SingleNode reverse(SingleNode head) {
//Set starting point for iteration
SingleNode current = head;
//Since previous node for the 1st element will always be null originally
SingleNode previous = null;
SingleNode next = null;
while(current!=null) {
//Store next element node
next = current.next;
//Set the previous element as the next element for the node
current.next = previous;
//Set current element as the previous element,
//since we will be moving ahead
previous = current;
//For going to the next node
current = next;
}
//The final previous value would be the last value
//in the original list and the first value in the reversed list
SingleNode newHead = previous;
return newHead;
}
From complexity perspective, this will be O(n) from time complexity as we are iterating over the given list only once. From space complexity it will be O(1) since there is no additional space used for processing using the iterative approach.
RECURSIVE
The recursive way could be challenging to understand at first. We will talk through the code one by one to understand what exactly we are doing. First let's have a look at the code and then dissect it to get more clarity.
public static SingleNode reverseRecursively(SingleNode head) {
if(head==null || head.next==null)
return head;
SingleNode newHead = reverseRecursively(head.next);
head.next.next = head;
head.next=null;
return newHead;
}
So, let's say we have a linked list like 10 > 11 > 12 > 13 > 14
SingleNode newHead = reverseRecursively(head.next);
For first element node with value 10
It will go for the above line of code and send the next element node which is 11
It will go for the above line of code and send the next element node which is 12
It will go for the above line of code and send the next element node which is 13
So, our recursive call stack will look something like this,
Now when it comes to the call 5, it will satisfy the below if condition and return back the last node acting as the new head.
if(head==null || head.next==null)
return head;
Now we have to understand this that with each recursive call a smaller version of the linked list is being sent
When this happens, our call stack will be reduced by 1, we will be now at call 4.
For call 4, we will go for below lines
which follows the recursive dialogue which is I will be my next element's next element which is summarized by below line of code.
head.next.next = head;
So, element node with value 13 will say, I will be my next element's (14), next element which would help us create 14 > 13. Similarly, element node with value 12 will say I will be my next element's (13), next element which would help us create 13 > 12 and this will continue till it reaches element 10, which will be the last element and for the last element, the next would be null. Hence the below line of code.
head.next=null;
Visually something like below would happen. We have to understand that the pointing is to the memory address of the node and not the node value.
At Node with value 13
At Node with value 12
At Node with value 11
At Node with value 10 (Final Transformation)
And once we have understood this representation meant for recursive approach, visually imagining the iterative one is kind of easy. And definitely going through the article Understanding Linked List helps.
The complexity will change when it comes to the recursive approach, this will still be O(n) from time complexity as we are iterating over the given list only once. However, when we look at space complexity it will be O(n), due to recursive calls multiple call stack would have to be looked at.
Well, that's about reversing a singly linked list, wonder what we would do for doubly linked list?? Ain't a rocket science since the only change in doubly linked list is along with the next we need to also have a previous pointer. So, with regards to the iterative approach it will be
My Previous Is My Next And I Am Previous Of My Next
public static DoubleNode reverse(DoubleNode head) {
DoubleNode current = head;
DoubleNode previous = null;
DoubleNode next = null;
while(current!=null) {
//Store previous element node, for 1st element it will be null
previous = current.prev;
//Store next element node
next = current.next;
//Set the previous element as the next element for the node
current.next = previous;
current.prev = next;
//Set current element as the previous element,
//since we will be moving ahead
previous = current;
//For going to the next node
current = next;
}
//The final previous value would be the last value
//in the original list and the first value in the reversed list
DoubleNode newHead = previous;
return newHead;
}
For recursive approach, it would be I Will Be My Next Element's Next Element And My Previous Will Be My Next Element
public static DoubleNode reverseRecursively(DoubleNode head) {
if(head==null || head.next==null || head.prev==null)
return head;
DoubleNode newHead = reverseRecursively(head.next);
head.prev = head.next;
head.next.next = head;
head.next=null;
return newHead;
}
Was simple to get it, wasn't it?? Well, that's about the conversation with the code we are going to have for now... We all need a break. Until next time!!
Powered by Froala Editor