Reverse a Linked list data structure in java

Linked List or Singly Linked List is a type of data structure. In a  linked list, each node stores the contents and a pointer (reference) of the next node. Reverse a Linked list is important to understand the flexibility and usability of Linked List.

Question :

Given the pointer to the head node of a linked list, the task is to reverse the linked list. You need to reverse the list by changing links between nodes.

Example :

Given Linked list : -> 4-> 2-> 7-> 9-> 1
Reverse Linked list : -> 1-> 9-> 7-> 2-> 4

Solutions : Iterative Method

1. Initialise three pointers

currentNode = head;  nextNode = null;  previousNode = null;

2. Iterate trough the linked list. In while loop, do following.

//store next node
currentNode = currentNode->nextNode

// Revers node pointers

currentNode -> next = previousNode 

// Move previous and current node one step forward
previousNode =currentNode
currentNode = nextNode

Completed code :

package in.eyehunt.data.struc;

public class LinkedList {

    Node head; // head of list

    // Linked list Node.
    class Node {
        int data;
        Node next;

        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }

    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }

    void reverseLinkedList() {

        Node currentNode = head;
        Node nextNode = null;
        Node previousNode = null;
        while (currentNode !=null){
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        head = previousNode;
        printAllNodes("\nReverse Linked list : ");
    }

    void printAllNodes(String mesg) {
        Node node = head;
        System.out.print(mesg);
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }

    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes("Given Linked list : ");
        linkedList.reverseLinkedList();
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

Reverse a linked list is top in list of java interview question, so do practice more… here is more LinkedList interview questions :

1. Program for n’th node from the end of a Linked List
2. Find the middle of a given linked list data structure
3. Inserting a new node in a linked list data structure
4. Find Length of a Linked List data structure (Iterative and Recursive)