How to Reverse Linked List in Java?

• Introduction
• Recursive Approach(Algorithms, Code and Output)
• Iterative Approach(Algorithms, Code and Output)
• Frequently Asked Questions on Reversed Linked List

Introduction

A reversed linked list is the opposite of a linked list. So, we will first see what a linked list is. A linked list is a type of data structure that consists of data and a pointer in which the pointer points to the next node is called a linked list. In simple language, we can say that a linked list is a data structure in which the data items are connected via links where each link is connected to another link. And when such a linked list is reversed, it is called Reversed Linked List. In a reversed linked list, the list is divided into two parts, such as the first part is the first node of the list, and the second part is the rest of the linked list. The last node is connected with the first node, and the first node is fixed. 

The linked list is a fundamental data structure that has subtypes such as stack and queues. Several operations can be performed in a reversed linked list, just like we do in the simply linked list like Insertion, deletion, updating, etc. 

In this article, we are going to understand some useful examples with their basic concepts. We will also see the implementation of Reverse Linked List in various programming languages that will help you better understand the logic behind its implementation. 

Recursive Approach(Algorithms, Code and Output)

To apply the recursive approach for a reverse linked list, we are required to divide the linked list into two different parts such as the first node and the remaining list. After that, we can call the recursion for the other part of the list that maintains the connection between nodes. 

The picture below depicts what exactly the recursive approach does:

• Implementation: Now, let us see the implementation of the Reverse Linked list in various programming languages using the recursive approach below. But, first, we will see the common algorithm that is used in the recursive approach:

Algorithm:

• Divide the Linked list into two parts where the first part is the first node and the second part is the remaining list.
• Call the recursion for the rest of the linked list to make it in reversed order.
• Link the rest of the list with the first node.
• Set the head pointer to the first node only.

As we just see how the algorithm of Reverse linked list for recursion works, now let us see its implementation in some common programming languages. 

• In C++ : 

#include <iostream>
#include <vector>
using namespace std;
struct LinkNode
{
    int data;
    LinkNode * next;
};
void printList(LinkNode * head)
{
    LinkNode * pointer = head;
    while (pointer)
    {
        cout << pointer->data << " —> ";
        pointer = pointer->next;
    }
    cout << "nullPointer" << endl;
}
void push(LinkNode * &headRef, int data)
{
    LinkNode* newNode = new LinkNode();
    newNode->data = data;
    newNode->next = headRef; 
    headRef = newNode;
}
void reverseLinked(LinkNode * head, LinkNode * &headRef)
{
    LinkNode * first;
    LinkNode * rest;
    if (head == nullPointer) {
        return;
    }
    first = head;          
    rest = first->next;    
    if (rest == nullPointer)
    {
        headRef = first;
        return;
    } 
    reverseLinked(rest, headRef);
    rest->next = first;
    first->next = nullPointer; 
}
 
void reverse(LinkNode* &headRef) {
    reverseLinked(headRef, headRef);
}
int main()
{
    vector<int> keys = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    LinkNode * head = nullPointer;
    for (int i = keys.size() - 1; i >=0; i--) {
        push(head, keys[i]);
    }
    reverse(head);
    printList(head);
    return 0;
}

Output

9 -> 8 -> 7 -> 6 —> 5 —> 4 —> 3 —> 2 —> 1 —> nullPointer

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

In Java

class LinkNode
{
    int data;
    LinkNode next;
 
    LinkNode(int data) {
        this.data = data;
    }
}
 
class Main
{
  
    public static void printList(LinkNode head)
    {
        LinkNode pointer = head;
        while (pointer != null)
        {
            System.out.print(pointer.data + " —> ");
            pointer = pointer;
        }
        System.out.println("null");
    }
 
   
    public static LinkNode push(LinkNode head, int data)
    {
        LinkNode node = new LinkNode(data);
        node.next = head;
        return node;
    }
 
  
    public static LinkNode reverse(LinkNode head, Node firstNode)
    {
        LinkNode first, rest; 
        if (head == null) {
            return firstNode;
        } 
        first = head;           
        rest = first.next;      
        if (rest == null)
        {  
            firstNode = first;
            return firstNode;
        }
        firstNode = reverse(rest, firstNode);
        rest.next = first;
        first.next = null; 
 
        return firstNode;
    }
    public static LinkNode reverse(LinkNode head) {
        return reverse(head, head);
    }
    public static void main(String[] args)
    {
        int[] keys = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        LinkNode head = null;
        for (int i = keys.length - 1; i >=0; i--) {
            head = push(head, keys[i]);
        }
 
        head = reverse(head);
        printList(head);
    }
}

Output: 

9 -> 8 -> 7 -> 6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null 

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

In Python

class LinkNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
def printLnkdLst(head):
    ptr = head
    while ptr:
        print(ptr.data, end=' —> ')
        ptr = ptr.next
    print('None') 
def reverse(head, firstNode): 
    if head is None:
        return firstNode 
    first = head               
    rest = first.next 
    if rest is None:   
        firstNode = first
        return firstNode
    firstNode = reverse(rest, firstNode)
    rest.next = first
    first.next = None
    return firstNode
def reverseLnkdList(head):
    return reverse(head, head)
if __name__ == '__main__':
    head = None
    for i in reversed(range(9)):
        head = LinkNode(i + 1, head)
    head = reverseLnkdList(head)
    printLnkdLst(head)

Output: 

9 -> 8 -> 7 -> 6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None

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

Iterative Approach(Algorithms, Code and Output)

Algorithm: 

In this approach, three-pointers will be initialized first.

Iterate in the linked list until it is not empty.

Return the previous pointer that will work as the first node for the reversed linked list. 

The other pointers are also repeated iteratively until it reaches the end of the linked list. 

The final list will be a reversed linked list. 

Implementation 

In C++

#include<bits/stdc++.h>
 
using namespace std;
 
struct linkednode {
    int data;
    struct linkednode * next;
};
void push(struct linkednode **head_ref, int data) {
    struct linkednode *linkednode;
    linkednode = (struct linkednode*)malloc(sizeof(struct linkednode));
    linkednode->data = data;
    linkednode->next = (*head_ref);
    (*head_ref) = linkednode;
}
void reverse(struct linkednode **head_ref) {
    struct linkednode *temp = NULL;
    struct linkednode *prev = NULL;
    struct linkednode *current = (*head_ref);
    while(current != NULL) {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    (*head_ref) = prev;
}

void printallnodes(struct linkednode *head) {
    while(head != NULL) {
        cout<<head->data<<" ";
        head = head->next;
    }
}
int main() {
    struct linkednode *head = NULL;
    push(&head, 0);
    push(&head, 1);
    push(&head, 8);
    push(&head, 0);
    push(&head, 4);
    push(&head, 6);
    push(&head, 9);
    push(&head, 10);
    cout << "Before Reversing the Linked List: " << endl;
    printallnodes(head);
    reverse(&head);
    cout << endl;
    cout << "After Reversing the Linked List: "<<endl;
    printallnodes(head);
    return 0;

Output: 

Before Reversing the Linked List:

10 9 6 4 0 8 1 0

After Reversing the Linked List:

0 1 8 0 4 6 9 10

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

In Java

class LinkedNode
{
    int data;
    LinkedNode next;
 
    LinkedNode(int data, LinkedNode next)
    {
        this.data = data;
        this.next = next;
    }
}
 
class Main
{

    public static void printLinkedList(LinkedNode firstNode)
    {
        LinkedNode pointer = firstNode;
        while (pointer != null)
        {
            System.out.print(pointer.data + " —> ");
            pointer = pointer.next;
        }
 
        System.out.println("null");
    }
 

    public static LinkedNode reverse(LinkedNode firstNode)
    {
        LinkedNode previous = null;
        LinkedNode current = firstNode;
 

        while (current != null)
        {

            LinkedNode next = current.next;
 
            current.next = previous;    
 
            previous = current;
            current = next;
        }
 

        return previous;
    }
 
    public static void main(String[] args)
    {

        int[] keys = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        LinkedNode firstNode = null;
        for (int i = keys.length - 1; i >= 0; i--) {
            firstNode = new LinkedNode(keys[i], firstNode);
        }
 
        firstNode = reverse(firstNode);
        printLinkedList(firstNode);
    }
}

Output: 

9 -> 8 -> 7 -> 6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null 

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

In Python

class LinkedNode:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
def printLinkedList(head):
    pointer = head
    while pointer:
        print(pointer.data, end=' —> ')
        pointer = pointer.next
    print('None')
def reverse(head):
    previous = None
    current = head
    while current:
        next = current.next 
        current.next = previous        
 
        previous = current
        current = next
    return previous
if __name__ == '__main__':
    head = None
    for i in reversed(range(9)):
        head = LinkedNode(i + 1, head)
    head = reverse(head)
    printLinkedList(head)

Output: 

9 -> 8 -> 7 -> 6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None
Time Complexity: O(n) 
Space Complexity: O(1)

Frequently Asked Questions on Reversed Linked List

Conclusion

The linked list is a very useful data structure and because of its importance reverse linked list also has its importance in specific cases. In this article, we discussed the concept of how we can reverse a linked list by two approaches i.e. recursive and iterative. Both of the approaches are very useful. We also discussed the algorithms and their application in different programming languages that helped to better understand the logic behind reversing a linked list.