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.
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
1
2
3
4
After
4
3
2
1
