There are a couple of algorithms exists to reverse a singly linked list in Java e.g. You can use the three-pointers approach or solve this problem using a stack, or simply using recursion without the external stack. As I had pointed out on the earlier post about linked list, that reversing a linked list is one of the most popular data structure interview question, based on linked list, which means, you just can't afford to prepare this one, before going for any programming interview. Despite being so common, It's not easy to solve this problem on the fly. Many Java programmer struggles to reverse a linked list using both iteration and recursion, which makes this question very useful for filtering programmers who can code and who are not so good with coding. Indeed, this is one of the confusing algorithms to understand and it's not easy to grasp, especially if you haven't practiced linked list based questions e.g. finding middle node of linked list in one pass or inserting and removing an element from linked list data structure.

Since Java programmer gets a linked list implementation in the form of java.util.LinkedList, they never bother to do this exercise by hand. Yes, there are some exceptions but many Java programmer doesn't focus enough on data structure and hand coding, which is really important to improve your problem-solving skills for the interview.

So, when it comes to design a whole system using Object oriented analysis and design e.g. implementing a vending machine in Java, sometimes they fail to choose the correct data structure and devising simple algorithms.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithm as possible to take advantage of all the knowledge available. This will improve your thinking ability, problem-solving skill and you will be more comfortable with dealing with the unknown set of problems. This advice is irrespective of whether you are a Java, C++, or Python developer.

##

A linked list is a data structure which contains nodes, every node keep data and pointer to next node. This way linked list grows and can store as many elements as much memory allows it. It's not like an array which requires a contiguous chunk of memory because here node can be stored at any memory location.

This structure means, adding and removing elements in linked list is easy but searching an element is expensive because you need to traverse entire list to find the element. It doesn't help even if you know that element is the 5th node or 6th node because you cannot access them by index like an array. This is the biggest difference between an array and linked list data structure. In the array, searching the index is O(1) operation but in linked list searching is O(n) operation.

Below code represent a singly linked list in Java, with limited operations. I have already removed some non-relevant code for performing different operations on linked list i.e. checking if linked list is cyclic or not, inserting an element at the middle, and removing the element. Since we don't need this code for reversing linked list, I have simply deleted them for now.

This class is similar to the SinglyLinkedList class, which we have seen in how to implement linked list in Java using generics (see here), with two more methods for reversing linked list using iteration and recursion.

The reverseRecursively() method reverse the linked list using recursion. It uses the call stack to store data, and once we reached tail, which becomes new head for the reversed linked list, it starts adding nodes in reverse order. Look at some comments around those methods, which will make you understand the algorithm of reversing linked list better.

The reverseIteratively() method reverses linked list using the three-pointers approach and using loops, that's why it is called iterative solution. It traverses through the linked list and adding nodes at the beginning of the singly linked list in each iteration. It uses three reference variables (pointers) to keep track of previous, current, and next nodes.

If you are not very familiar with linked list data structure or want to learn more about linked list data structure, you should first read a good book on data structure and algorithm e.g. Data Structures and Algorithms Made Easy in Java by Narasimha Karumanchi, one of the best books to learn data structure and algorithms.

###

###

Here is our test class, which will test both methods of reversing linked list, reverseIteratively() and reverseRecursively(). We have first created a singly linked list with 6 nodes A-B-C-D-E-F, and first reversed them iteratively using 3 points approach and later reversed the same list recursively. Since the same instance of the singly linked list is reversed two times, you can see in the output that final list is same as original linked list.

That's all on

Related

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Thanks for reading this interview question. If you like this article then please share with your friends and colleagues. If you have any suggestions or feedback then please share your comment.

Since Java programmer gets a linked list implementation in the form of java.util.LinkedList, they never bother to do this exercise by hand. Yes, there are some exceptions but many Java programmer doesn't focus enough on data structure and hand coding, which is really important to improve your problem-solving skills for the interview.

So, when it comes to design a whole system using Object oriented analysis and design e.g. implementing a vending machine in Java, sometimes they fail to choose the correct data structure and devising simple algorithms.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithm as possible to take advantage of all the knowledge available. This will improve your thinking ability, problem-solving skill and you will be more comfortable with dealing with the unknown set of problems. This advice is irrespective of whether you are a Java, C++, or Python developer.

##
__Java Program to Reverse a singly linked list using recursion and Iteration__

A linked list is a data structure which contains nodes, every node keep data and pointer to next node. This way linked list grows and can store as many elements as much memory allows it. It's not like an array which requires a contiguous chunk of memory because here node can be stored at any memory location.This structure means, adding and removing elements in linked list is easy but searching an element is expensive because you need to traverse entire list to find the element. It doesn't help even if you know that element is the 5th node or 6th node because you cannot access them by index like an array. This is the biggest difference between an array and linked list data structure. In the array, searching the index is O(1) operation but in linked list searching is O(n) operation.

Below code represent a singly linked list in Java, with limited operations. I have already removed some non-relevant code for performing different operations on linked list i.e. checking if linked list is cyclic or not, inserting an element at the middle, and removing the element. Since we don't need this code for reversing linked list, I have simply deleted them for now.

This class is similar to the SinglyLinkedList class, which we have seen in how to implement linked list in Java using generics (see here), with two more methods for reversing linked list using iteration and recursion.

The reverseRecursively() method reverse the linked list using recursion. It uses the call stack to store data, and once we reached tail, which becomes new head for the reversed linked list, it starts adding nodes in reverse order. Look at some comments around those methods, which will make you understand the algorithm of reversing linked list better.

It is said that a picture is worth a thousand word and it is very true in the case of problem-solving and understanding algorithms. Here are a diagram and flowchart to reverse a singly linked list using recursion. It divides the list into two parts first node and rest of list, and then link rest to head in reverse order. It then recursively applies same division until it reaches the last node, at that point whole linked list, is reversed.

If you are not very familiar with linked list data structure or want to learn more about linked list data structure, you should first read a good book on data structure and algorithm e.g. Data Structures and Algorithms Made Easy in Java by Narasimha Karumanchi, one of the best books to learn data structure and algorithms.

###
__Java Class to represent Singly Linked List__

Here is our Java program solve this problem. As I said, it contains a class to represent singly linked list and it contains another class which has the main method for testing. That class creates an instance of linked list and then call relevant methods to reverse the linked list by using iteration and recursion.

/** * Java Class to represent singly linked list for demonstration purpose. * In order to understand How to reverse linked list, focus on two methods * reverseIteratively() and reverseRecursively(). * @author Javin Paul */ public class SinglyLinkedList { private Node head; // Head is the first node in linked list public void append(T data){ if(head == null){ head = new Node(data); return; } tail().next = new Node(data); } private Node tail() { Node tail = head; // Find last element of linked list known as tail while(tail.next != null){ tail = tail.next; } return tail; } @Override public String toString(){ StringBuilder sb = new StringBuilder(); Node current = head; while(current != null){ sb.append(current).append("-->"); current = current.next; } if(sb.length() >=3){ sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node } return sb.toString(); } /** * Reverse linked list using 3 pointers approach in O(n) time * It basically creates a new list by reversing direction, and * subsequently insert the element at the start of the list. */ public void reverseIteratively() { Node current = head; Node previous = null; Node forward = null; // traversing linked list until there is no more element while(current.next != null){ // Saving reference of next node, since we are changing current node forward = current.next; // Inserting node at start of new list current.next = previous; previous = current; // Advancing to next node current = forward; } head = current; head.next = previous; } /* * Reverse a singly linked list using recursion. In recursion Stack is * used to store data. * 1. Traverse linked list till we find the tail, * that would be new head for reversed linked list. */ private Node reverseRecursively(Node node){ Node newHead; //base case - tail of original linked list if((node.next == null)){ return node; } newHead = reverseRecursively(node.next); //reverse the link e.g. C->D->null will be null node.next.next = node; node.next = null; return newHead; } public void reverseRecursively(){ head = reverseRecursively(head); } private static class Node { private Node next; private T data; public Node(T data) { this.data = data; } @Override public String toString() { return data.toString(); } } }

###
__Test Class__

Here is our test class, which will test both methods of reversing linked list, reverseIteratively() and reverseRecursively(). We have first created a singly linked list with 6 nodes A-B-C-D-E-F, and first reversed them iteratively using 3 points approach and later reversed the same list recursively. Since the same instance of the singly linked list is reversed two times, you can see in the output that final list is same as original linked list./** * Java program to test code of reversing singly linked list in Java. * This test class test both iterative and recursive solution. Since * the same list is first reversed using loops, and then again using recursion. * You can see that final output is same as original linked list. * @author Javin Paul */ public class SinglyLinkedListTest { public static void main(String args[]) { SinglyLinkedList linkedlist = getDefaultList(); System.out.println("linked list before reversing : " + linkedlist); linkedlist.reverseIteratively(); System.out.println("linked list after reversing : " + linkedlist); linkedlist.reverseRecursively(); System.out.println("linked list after reversing recursively: " + linkedlist); } private static SinglyLinkedList getDefaultList(){ SinglyLinkedList linkedlist = new SinglyLinkedList(); linkedlist.append("A"); linkedlist.append("B"); linkedlist.append("C"); linkedlist.append("D"); linkedlist.append("E"); linkedlist.append("F"); return linkedlist; } } Output: linked list before reversing : A-->B-->C-->D-->E-->F linked list after reversing : F-->E-->D-->C-->B-->A linked list after reversing recursively: A-->B-->C-->D-->E-->F

That's all on

**how to reverse a linked list in Java**. We have seen two approaches to reverse singly linked list, first using Iterations, which involves 3 pointers or reference variable; and second, which reversed linked list using recursion. The reason, I have shared both approaches because they are asked as a follow-up question, and it's always better to know both approaches to make a good impression. By the way, if you can improve the algorithm, and can find few more ways to reverse linked list, will always act as plus point for you. You can also check out Cracking the code interview 6th Edition for more practice questions. It contains 189 coding interview questions based upon data structure, algorithms, and other topics.Related

**linked list and data structure questions**you may like to explore- When to use ArrayList vs LinkedList in Java? (answer)
- How to convert linked list to an array in Java? (example)
- How to find the first and last element of linked list in Java? (solution)
- How to search element inside linked list in Java? (solution)
- What is the difference between LinkedList and ArrayList in Java? (answer)
- How to reverse an array in place in Java? (solution)
- Top 30 Array-based Interview Questions for Programmers (list)
- Top 5 Books to Learn Data Structure and Algorithms (books)
- Top 5 Books for Programming and Coding Interviews (books)

**Further Learning**

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Thanks for reading this interview question. If you like this article then please share with your friends and colleagues. If you have any suggestions or feedback then please share your comment.

## 3 comments :

hey you are wrong, we can access thru the index

public class LinkedListDemo {

public static void main(String[] args) {

// create a LinkedList

LinkedList list = new LinkedList();

// add some elements

list.add("Hello");

list.add(2);

list.add("Chocolate");

list.add("10");

// print the list

System.out.println("LinkedList:" + list);

// print element at index 3

System.out.println("Element at index 3 :" + list.get(3));

}

}

Thank you for illustration.

@Common man protection force,

Linkedlist API is provided with index based access but it doesn't work like array, if you check internal logic of get(index) method, you will find, internally Linkedlist iterate through each element upto index

But in case of array, you can directly go to specific index.

## Post a Comment