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 :

package com.alychidesigns.list;

/**
 * @author 
 */
public class Node {
    private int value;
    private Node next;

    public Node(int value) {
        this.value = value;
    }

    public static Node createLinkedListFromArray(int... data) {
        Node root = null;
        if (data != null && data.length > 0) {
            Node node = new Node(data[0]);
            root = node;
            for (int i = 1; i < data.length; i++) {
                node.setNext(new Node(data[i]));
                node = node.getNext();
            }
        }
        return root;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        Node root = this;
        while (root != null) {
            stringBuilder.append(root.getValue()).append(",");
            root = root.getNext();
        }
        return stringBuilder.toString();
    }
}

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

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

package com.alychidesigns.list.reverse;

import com.alychidesigns.list.Node;

/**
 * @author 
 */
public interface Reverser {
    Node reverse (Node node);
}

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:

package com.alychidesigns.list.reverse;

import com.alychidesigns.list.Node;

/**
 * @author 
 */
public class RecursionReverser implements Reverser {
    @Override
    public Node reverse(Node node) {
        if( node == null)
            return node;
        Node next = node.getNext();
        if(next == null)
            return node;
        node.setNext(null);
        Node reverseList = reverse(next);
        next.setNext(node);
        return reverseList;
    }
}

Pros: