Sunday, 29 December 2013

How to reverse a LinkedList in Java?

A very basic interview question asked. In an earlier post we had see the LinkedList class in java and how to reverse it using Collections.revere(). You can refer to that post. Point to note that the LinkedList class defined in java is infact a doubly Linked list and that is not what the interviewer will be interested in.  Yes you can give that as your 1st answer as it will depict you have java knowledge but at some point you will have to fall back to basics.

Before we write the code to actually reverse the LinkedList lets write the code for the LLNode  data structure which will form our LinkedList.

LinkedList Node 

public class LLNode {

    int value;
    LLNode nextNode;

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

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public LLNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(LLNode nextNode) {
        this.nextNode = nextNode;
    }

    public static void printLL(LLNode head){
        if (head != null){
            System.out.println(head.getValue());
            printLL(head.getNextNode());
        }
    }
}

Note : In this data structure we have also provided a method printLL() to print the Linked List.

Now lets go ahead and write our code to reverse this Linked List

Linked List Reversal

public class LLReverser {

    public static LLNode reverse(LLNode root){

        if(root.getNextNode() == null){
            return root;
        }

        LLNode next = root.getNextNode();
        root.setNextNode(null);

        while(next != null){
            LLNode temp = null;
            if(next.getNextNode() != null)
                temp = next.getNextNode();
            next.setNextNode(root);
            root = next;
            next = temp;
        }

        return root;

    }
}

Now let us test it out

Testing the logic

    public static void main(String args[]){

        LLNode root = new LLNode(1);
        LLNode second = new LLNode(2);
        root.setNextNode(second);
        LLNode third = new LLNode(3);
        second.setNextNode(third);
        LLNode fourth = new LLNode(4);
        third.setNextNode(fourth);

        System.out.println("Before");
        LLNode.printLL(root);
        System.out.println("After");
        LLNode.printLL(LLReverser.reverse(root));

    }

Output :

Before
1
2
3
4
After
4
3
2
1

No comments:

Post a comment

t> UA-39527780-1 back to top