Reverse Singly Linked List using Recursion implementation

Recently I’ve read IT topic about interview questions and was surprised, Programmers discussed about “hard” interview question “Reversing of Linked List”. Judging to that topic the task was hard for most candidates and I decided to write short note about Reversing Linked List.

  • Firstly this task was to Reverse Singly Linked List using recursion;
  • Secondly time for creating algorithm was about 5 mins;

So, I’ve used Java for realization but you can write the same code using C,C++ and other languages.

Ok, Lets go…

I’ve created new structure for Singly linked list :

Also, I’ve decided to create a few implementations and this structure will be used for all of them.

READ  How to debug deployed content model on Alfresco?

I’ve extracted common interface called Reverser with simple API for algorithm implementations:

After it, I’ve started to create first implementation.

So, First implementation is Recursion.

Steps of algorithm:

Go through all nodes and reverse them 🙂
Ok, seriously

  • Check if input Node is not null, if null return it {first rule to stop recursion}
  • Check if next Node is not null, if null return input node {second rule to stop recursion}
  • Get and save next Node
  • Set null as next value for input node
  • Call recursion method with next node and save result to reversed Node root
  • Set input Node as next to next Node 🙂
  • Return reversed Node root

Code:

Pros:

  • Simple to implement
  • You can see all process of reversing
  • You can understand recursion 🙂

Cons:

  • Usage of Stack Memory
  • As result can be thrown StackOverflowError
READ  How to use If-Else in Mysql

It’s first implementation of reverse functionality for LinkedList, I am going to add a few other ways of implementation in next posts.

Thanks.

Leave a Reply

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