## Wednesday, May 4, 2022

### Question 48: How to reverse linked list in java

You need to write iterative and recursive solution to reverse linked list

## Iterative

The logic for this would be

 Have three nodes i.e `previousNode`,`currentNode` and `nextNode` When `currentNode` is starting node, then `previousNode` will be null Assign `currentNode.next` to `previousNode` to reverse the link. In each iteration move `currentNode` and `previousNode` by 1 node.

``````public static Node reverseLinkedList(Node currentNode)
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
nextNode=currentNode.next;
currentNode.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}``````

Java program to reverse a linkedlist will be :

``````public class LinkedList{

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

} else {
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}

while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// Reverse linkedlist using this function
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
nextNode=currentNode.next;
currentNode.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}

public static void main(String[] args) {

System.out.println("After reversing");

}

}``````
Run above program, you will get following output:
``````5 6 7 1 2
After reversing
2 1 7 6 5``````

## Recursive

Base case: The base case for this would be either node is null or node. next is null
For recursive solution, replace reverse linked list of above program to below function

``````public static Node reverseLinkedList(Node node) {
if (node == null || node.next == null) {
return node;
}

node.next.next = node;
node.next = null;
return remaining;
}``````

Output of this program will be same as above program.
Now lets understand logic for above recursive program.
`5->6->7->1->2`

Above function will terminate when last `node(2)`‘s `next` will be `null`.so while returning when you reach at node with value `1`,If you closely observe `node.next.next=node` is actually setting `2->1`(i.e. reversing the link between node with value 1 and 2) and `node.next=null`is removing link `1->2`

So in each iteration, you are reversing link between two nodes.
Below diagram will make it clear

Don't miss the next article!

Be the first to be notified when a new article or Kubernetes experiment is   published.