#### Tutorial

Published on August 3, 2022

Anupam Chugh

Reversing a Linked List is an interesting problem in data structure and algorithms. In this tutorial, we’ll be discussing the various algorithms to reverse a Linked List and then implement them using Java.

LinkedList is a data structure which stores the data in a linear way. Though not in a contiguous way. Every element of a LinkedList contains a data part and an address to the next element of the LinkedList. LinkedList elements are popularly known as nodes.

In order to reverse a LinkedList in place, we need to reverse the pointers such that the next element now points to the previous element. Following is the input and output. [caption id=“attachment_23038” align=“aligncenter” width=“333”] Input[/caption] [caption id=“attachment_23039” align=“aligncenter” width=“327”] Output[/caption] The head of the LinkedList is the first node. No other element has the address stored for this. The tail of the LinkedList is the last node. The next address stored in this node is `null`. We can reverse a LinkedList such that the head and tail also get changed using:

• Iterative Approach
• Recursive Approach

### Iterative Approach to Reverse a Linked List

To reverse a LinkedList iteratively, we need to store the references of the next and previous elements, so that they don’t get lost when we swap the memory address pointers to the next element in the LinkedList. Following illustration demonstrates how we will reverse our LinkedList by changing the references.

Following are the steps to be followed to reverse a LinkedList. Create 3 instances: current, next, previous. Loop the following till current is NOT null:

• Save the next Node of the current element in the next pointer.
• Set the next of the `current` Node to the `previous`. This is the MVP line.
• Shift previous to current.
• Shift the current element to next.

In the end, since the current has gone one place ahead of the last element, we need to set the head to the last element we reached. This is available in previous. Set head to previous. Thus we have our new head of the LinkedList which is the last element of the older LinkedList.

Here is a very simple implementation of LinkedList. Note that this is not a production-ready implementation and we have kept it simple so that our focus remains on the algorithm to reverse the Linked List.

``````package com.journaldev.linkedlist.reverse;

public static class Node {

Node next;

Object data;

Node(Object data) {
this.data = data;
next = null;
}
}
}
``````

The Java Program to reverse a Linked List iteratively and printing its elements is given below:

``````package com.journaldev.linkedlist.reverse;

public static void main(String[] args) {

}

}
System.out.println();
}

Node previous = null;
Node next;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
}

}
``````

Output:

``````1 2 3
3 2 1
``````

### Reverse a Linked List Recursively

To reverse a LinkedList recursively we need to divide the LinkedList into two parts: head and remaining. Head points to the first element initially. Remaining points to the next element from the head.

We traverse the LinkedList recursively until the second last element. Once we’ve reached the last element set that as the head. From there we do the following until we reach the start of the LinkedList. `node.next.next = node;` `node.next = null;` To not lose a track of the original head, we’ll save a copy of the head instance.

Following is the illustration of the above procedure. The Java program to reverse a LinkedList recursively is:

``````public static Node recursiveReverse(Node head) {
Node first;

return first;
}
``````

We just pass the head.next in the recursive call in order to go to the end of the LinkedList. Once we reach the end, we set the second last element as the next of the last element and set the next pointer of second last element to NULL. The last element will be marked as the new head. Use the following code to reverse the linked list using the recursive approach.

``````myLinkedList.head = recursiveReverse(myLinkedList.head);
``````

The output will remain as the previous iterative approach.

## Space Time Complexity of Reversing a Linked List

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

You can checkout complete code and more DS & Algorithm examples from our GitHub Repository.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Anupam Chugh

author

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

#### Still looking for an answer?

Ask a questionSearch for more help

JournalDev
DigitalOcean Employee
March 8, 2019

Looks like you haven’t tested your recursive solution…null pointer exception will be thrown for size 1.

- aj

Click below to sign up and get \$200 of credit to try our products over 60 days!

## Featured on Community

### Hollie's Hub for Good

Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

### Become a contributor

Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

## Welcome to the developer cloud

DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.