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;
            // reversing the link
            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 Node head;
 
    private static class Node {
        private int value;
        private Node next;
 
        Node(int value) {
            this.value = value;
 
        }
    }
 
    public void addToTheLast(Node node) {
 
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
 
            temp.next = node;
        }
    }
 
    public void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
 
    // Reverse linkedlist using this function
    public static Node reverseLinkedList(Node currentNode)
    {
        // For first node, previousNode will be null
        Node previousNode=null;
        Node nextNode;
        while(currentNode!=null)
        {
            nextNode=currentNode.next;
            // reversing the link
            currentNode.next=previousNode;
            // moving currentNode and previousNode by 1 node
            previousNode=currentNode;
            currentNode=nextNode;
        }
        return previousNode;
    }
 
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Creating a linked list
        Node head=new Node(5);
        list.addToTheLast(head);
        list.addToTheLast(new Node(6));
        list.addToTheLast(new Node(7));
        list.addToTheLast(new Node(1));
        list.addToTheLast(new Node(2));
 
        list.printList(head);
        //Reversing LinkedList
        Node reverseHead=reverseLinkedList(head);
        System.out.println("After reversing");
        list.printList(reverseHead);
 
    }
 
}

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 remaining = reverseLinkedList(node.next);
        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=nullis 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.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest