How to reverse a Singly Linked List iteratively and recursively

Linked List is a data structure that possess following properties:

  • The are a group of nodes linked together by some reference. Singly linked list has reference to next node, while doubly linked list has reference to previous and next nodes.
  • Elements can be inserted indefinitely.
  • They don’t take contiguous memory locations. For this reason, they are suitable to be used even if the disk or memory is fragmented.
  • They allow sequential access to elements while arrays allow random access
  • Extra space is needed for reference. It is impractical to use for boolean or char for space wastage.

Singly linked list might not be a right data structure for all situations, so a care must be taken in choosing the data structure for your problem. As the link in the singly linked list only points to the location of the next object (and not in reverser order), singly linked list can only be traversed in forward direction. Also, you need to know the location of the first node or object to be able to traverser rest of the nodes or objects.

In this article,  I have provided solutions coding for the following:

  • Reversing a singly linked list by using recursion – Recursive Reverse
  • Reversing a singly linked list by using iteration – Iterative Reverse.

Java Implementation Code:

package com.icodejava.blog.datastructure;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 28, 2014
 * Last Modified On - Feb 28, 2014
 */
public class LinkedListReverse {
	
	public static void main(String args[]) {
		
		//Preparing some linked list structure
		LinkedList linkedList = new LinkedList(5);
		linkedList.next = new LinkedList(4);
		linkedList.next.next = new LinkedList(3);
		linkedList.next.next.next = new LinkedList(2);
		linkedList.next.next.next.next = new LinkedList(1);

		System.out.println("Original Linked List: " + linkedList.toString());

		//recursively reverse and print
		linkedList = recursiveReverse(linkedList);
		System.out.println("Recursively Reversed List: "
				+ linkedList.toString());

		//iteratively reverse and print
		linkedList = iterativeReverse(linkedList);
		System.out.println("Iteratively Recursed to Original: "
				+ linkedList.toString());
	}

	/**
	 * This method uses recursive method to reverse a singly linked list.
	 */
	public static LinkedList recursiveReverse(LinkedList linkedList) {

		// check for empty or size 1 linked list. This is a base condition to
		// terminate recursion.
		if (linkedList == null || linkedList.next == null) {
			return linkedList;
		}

		LinkedList remainingReverse = recursiveReverse(linkedList.next);

		// update the tail as beginning
		LinkedList current = remainingReverse;
		while (current.next != null) {
			current = current.next;

		}
		// assign the head as a tail
		current.next = linkedList;
		linkedList.next = null;

		return remainingReverse;
	}

	/**
	 * This method uses iterative approach to reverse a singly linked list.
	 */
	public static LinkedList iterativeReverse(LinkedList linkedList) {

		if (linkedList == null || linkedList.next == null) {
			return linkedList;
		}

		LinkedList prevNode, currNode, nextNode;
		prevNode = null;
		nextNode = null;
		currNode = linkedList;

		while (currNode != null) {
			nextNode = currNode.next;
			currNode.next = prevNode;
			prevNode = currNode;
			currNode = nextNode;
		}

		return prevNode;
	}

}
/**
 * Custom Linked List representation class
 */
class LinkedList {
	public LinkedList next;
	public int value;

	public LinkedList(int value) {
		this.value = value;
		this.next = null;
	}

	@Override
	public String toString() {

		String data = "";
		LinkedList current = this;
		do {
			data += current.value + ",";
			current = current.next;
		} while (current != null);

		return data;
	}
}


Output of running above program:

Original Linked List: 5,4,3,2,1,
Recursively Reversed List: 1,2,3,4,5,
Iteratively Recursed to Original: 5,4,3,2,1,
  1. Implementing a Simple LIFO Stack in Java using LinkedList
  2. Implementing a Simple FIFO Queue in Java Using Linked List
  3. In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation
  4. Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation
  5. Array Max Integer Finder (With Big O Analysis)
  6. A Basic Implementation of Binary Tree in Java
  7. A Basic Implementation of Generic Tree in Java
  8. Basic example of implementing Singly Linked List in Java
  9. How to Add and Remove nodes in an unsorted Linked List
  10. Rotating a two dimensional integer array In-Place and using extra memory
  11. How to reverse a Singly Linked List iteratively and recursively
  12. Sorted Circular Linked List Implementation And Insert Operation
  13. Finding Mean Value Of An Integer Array In Java
  14. How to intersect two sets in Java using java.util.Set data structure.
  15. Bubble Sorting An Integer Array In Ascending and Descending Order
  16. How to split strings and separate the words with spaces
  17. How to easily sort characters in a String?
Tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *