Reversing a linked list is one of the famous interview questions, and many will stumble with this. It is not as simple as it sounds, need to take extra care while establishing the new links.
Lets assume we have a very basic "Node" class, which has one data field (int field) and one reference field to the next.
Also, we have a very basic LinkedList class which holds the 'head' of our LinkedList.
Assume, we have initialized our LinkedList with data 10->20->30->40->50, where 10 is the head. Our goal is to reverse this list, and the desired output would be 50->40->30->20->10
Recursive approach:
In general, understanding the recursion will take some time because of little complexity involved with the method stack. I am not going into too many details of the recursion here, but recursion helps us going to the very end of the list and back track from there.
This approach would give us the linear time and memory complexity which is O(n) in both the cases. The memory is O(n) because of the recursive call stack.
Here, lets go step by step.
Lets assume we have a very basic "Node" class, which has one data field (int field) and one reference field to the next.
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
Also, we have a very basic LinkedList class which holds the 'head' of our LinkedList.
public class LinkedList{
Node head;
public void add() {
....
}
public void remove() {
....
}
}
Assume, we have initialized our LinkedList with data 10->20->30->40->50, where 10 is the head. Our goal is to reverse this list, and the desired output would be 50->40->30->20->10
Recursive approach:
In general, understanding the recursion will take some time because of little complexity involved with the method stack. I am not going into too many details of the recursion here, but recursion helps us going to the very end of the list and back track from there.
public Node reverseRecursive(Node current) {
if(current == null || current.next == null) {
//This is our base case, we have reached the end of the list here, just return null
return current;
}
//recursive call, what is this method returning here? we need to make this method return the 'head' of a so far reversed List.
Node reversed = reverseRecursive(current.next);
//back tracking
//the following two lines are most important and most confusing parts of this approach. We will trace this down with the example
current.next.next = current;
current.next = null;
return reversed;
}
This approach would give us the linear time and memory complexity which is O(n) in both the cases. The memory is O(n) because of the recursive call stack.
Here, lets go step by step.
- How do we reveres a list with no items: we just return null (if(current == null) return current;)
- How do we reverse a list with one item: we just return the one item (it is already reversed)(if(current.next == null) return current;)
- How do we reverse a list with two items: Lets say our initial list 10 -> 20 -> null
- We need to reach to the end (recursive) (Node reversed = reverseRecursive(current.next);)
- Now in the stack, we have current as 10, current.next is 20
- Here we need to set 20.next = 10 correct? so current.next.next = current;
- Also, we need to remove the link between 10 and 20, that's why current.next = null;
- Last, but not least, we need to return the 'reversed', because that is our new head.
A little more explanation about those critical two lines, if somebody is still confused.
This time, lets a take a bigger list 10 -> 20 -> 30 -> 40 -> null.
stack 1 -> reverseRecursive(10) (current 10, current.next 20)
stack 2 -> reverseRecursive(20) (current 20, current.next 30)
stack 3 -> reverseRecursive(30) (current 30, current.next 40)
stack 4 -> reverseRecursive(40) (current 40, current.next null)
returns 40 (reversed is 40)
current.next.next = current; this becomes 30.next.next = 30; that means, 40.next = 30. (reversing the link)
current.next = null; this means 30.next = null
Here our intermediate list looks like this, 10 -> 20 -> 30 <- 40. (note: both 20's next and 40's next is pointing to 30)
Here, current.next.next = current; this becomes 20.next.next = 20; that means, 30.next = 20
Intermediate list here looks like 10 -> 20 <- 30 <- 40. (note: both 10's next and 30's next is pointing to 20)
In the final call stack, our list becomes 10 <- 20 <- 30 <- 40
In the final call stack, our list becomes 10 <- 20 <- 30 <- 40
current.next = null makes the list look like null <- 10 <- 20 <- 30 <- 40
If we observe, our 'reversed' never changed once we initialized for the first time which was with node 40, which is our new head. Hope this will make little clear.
Iterative approach:
It is straight forward, but need to pay attention to the little details. The idea would be keep track of the previous item in each iteration, point the current's next to the previous and re initialize previous with current.
With this approach, we get O(n) time complexity as we need visit each element in the list once, and O(1) memory complexity as we are storing one extra "next" variable.
Iterative approach:
It is straight forward, but need to pay attention to the little details. The idea would be keep track of the previous item in each iteration, point the current's next to the previous and re initialize previous with current.
public Node reverse(Node n) {
Node current= n;
Node previous = null;
while(current != null) {
Node next = current.next; //keep the reference of the next element as we are going to set the current.next to something else (previous)
current.next = previous; //back link, current's next should point to previous
previous = current; // make the current as previous (new intermediate header) for next iterations
current = next; // continue with the next
}
return previous; // this is our new header.
}
With this approach, we get O(n) time complexity as we need visit each element in the list once, and O(1) memory complexity as we are storing one extra "next" variable.
