Tutorial

Reverse a Linked List

Published on August 3, 2022
Default avatar

By Anupam Chugh

Reverse a Linked List

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.

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.

Reverse a Linked List

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.

Doubly LinkedList store two addresses. The address for the previous element and next element.

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”]linkedlist reverse input Input[/caption] [caption id=“attachment_23039” align=“aligncenter” width=“327”]linkedlist reverse output 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. linkedlist reverse iterative

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 class MyLinkedList {

	public Node head;

	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;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

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. linkedlist reverse recursive The Java program to reverse a LinkedList recursively is:

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

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	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.

Learn more about us


About the authors
Default avatar
Anupam Chugh

author

Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
March 8, 2019

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

- aj

    Try DigitalOcean for free

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

    Sign up

    Join the Tech Talk
    Success! Thank you! Please check your email for further details.

    Please complete your information!

    Get our biweekly newsletter

    Sign up for Infrastructure as a Newsletter.

    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.

    Learn more
    DigitalOcean Cloud Control Panel