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.

About these ads

4 thoughts on “Reverse LinkedList {Recursion implementation}

  1. Thank you. Great post! I’m really looking forward to learn about other ways you’ve mentioned. There must be more efficient one (as always).

    Maybe some of your readers will find helpful this page: http://goo.gl/q8nUS — that’s Python representation of your code in this fancy visualization/debugging tool where you could go step by step through execution process and on the right side see how state of your app is affected by every line of code.

    I’ve tried to minimize „noise” for viewers who may not be familiar with Python, so code is as simple as I could wrote, and without any helper methods (like createLinkedListFromArray() and toString()), but it’s working and idea is the same.

  2. Cool! One Step Can be Interchanged – For Slightly Better Performance and Lesser Code:

    // recursive reversal of linked list
    public LinkedList rReverse(LinkedList head) {

    LinkedList newHead=head.getNext(); <<<< next object is got here
    if(head==null || newHead==null) return head; <<<< this check here can be shortened into one line of code
    head.setNext(null);
    LinkedList val=rReverse(newHead);
    newHead.setNext(head);
    return val;
    }

    Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s