Reverse LinkedList {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 for Singly Linked List;
- 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.codingstories.list; /** * @author szagriichuk */ 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.codingstories.list.reverse; import com.codingstories.list.Node; /** * @author szagriichuk */ 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.codingstories.list.reverse; import com.codingstories.list.Node; /** * @author szagriichuk */ 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:
- 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
It’s first implementation of reverse functionality for LinkedList, I am going to add a few other ways of implementation in next posts.
Thanks.
