Given a LinkedList reverse it
1. Iterative.
2. Recursive.
1. Iterative.
2. Recursive.
/**
* @author vikky.agrawal
* Link List reversal | Iterative and Recursive.
*/
public class LinkedList {
Node node = null;
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.operations();
}
public void operations() {
this.node = new Node(10);
for (int i = 1; i < 6; i++) {
add(node, (int) (Math.random() * 100));
}
System.out.println("Test: iterative, List before reversal");
print(node);
this.node=reverse(node);
System.out.println("Test: recursive, List before reversal");
print(node);
this.node=this.recursiveReverse(node);
System.out.println("After recursice reverse list is : ");
print(node);
}
/**
* Reverse a linked list iterative.
* Using auxiliary pointers.
*/
public Node reverse(Node ptr) {
if (ptr == null) {
System.out.println("List is empty:returning");
return null;
}
Node ptr1 = ptr;
Node ptr2 = ptr;
Node ptr3 = null;
while (ptr1.getLink() != null) {
ptr2 = ptr1;
ptr1 = ptr1.getLink();
ptr2.setLink(ptr3);
ptr3 = ptr2;
}
ptr1.setLink(ptr2); //setting link for the last node;
System.out.println("Reversed List :");
this.print(ptr1);
return ptr1;
}
/**
* RecursiveReverse()
* Use cases:
* What is the reverse of null (the empty list)? null.
* What is the reverse of a one element list? the element.
* What is the reverse of an n element list?
* the reverse of the second element on
* followed by the first element.
*/
public Node recursiveReverse(Node root) {
// base case
if (root == null || root.getLink() == null) {
return root;
}
Node temp = recursiveReverse(root.getLink());
// temp contains last element when recursion done
// take 2 nodes and dry-run
root.getLink().setLink(root);
root.setLink(null);
return temp;
}
/**
* Print reverse of the link list
* reccursively
*/
public void printReverseRecursive(Node root){
if(root.getLink()!=null){
printReverseRecursive(root.getLink());
System.out.println(root.getData());
}else{
System.out.println(root.getData());
}
}
/**
* Helper functions for LinkedList
*/
public void add(Node ptr, int data) {
if (ptr == null) {
System.out.println("Always null ?");
ptr = new Node(data);
} else {
Node newptr = ptr;
while (newptr.getLink() != null) {
newptr = newptr.getLink();
}
newptr.setLink(new Node(data));
newptr.getLink().setLink(null);
}
}
public void print(Node ptr) {
if (ptr == null) {
return;
}
Node ptr1 = ptr;
System.out.print(ptr1.getData() + "->");
while ((ptr1 = ptr1.getLink()) != null) {
System.out.print(ptr1.getData() + "->");
}
System.out.println("/n");
}
public int size(Node ptr) {
if (ptr == null) {
return -1;
}
Node ptr1 = ptr;
int i = 1;
while ((ptr1 = ptr1.getLink()) != null) {
i++;
}
return i;
}
/**
* static inner class for LinkedList
* Data Structure
*/
private static class Node{
private int data;
private Node link;
Node(){
}
Node(int data){
//mergedList=new Node();
this.setData(data);
this.setLink(null);
}
public int getData(){
return this.data;
}
public Node getLink(){
return this.link;
}
public void setData(int data){
this.data=data;
}
public void setLink(Node link){
this.link=link;
}
}
}
