Reverse a Linked List

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”] 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 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. 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.