Reverse Linked List

https://www.geeksforgeeks.org/delete-nth-node-from-the-end-of-the-given-linked-list/

http://edgblog.wordpress.com/2007/12/06/reversing-a-singly-linked-list-in-java/

public class ReverseList {
public static void main(String args[]) {
// build a singly linked list
// a -> b -> c -> d -> e
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
Node d = new Node("d");
Node e = new Node("e");
a.next = b;
b.next = c;
c.next = d;
d.next = e;
SinglyLinkedList list = new SinglyLinkedList();
list.head = a;
System.out.println("Original list");
list.print(list.head);
list.reverse();
System.out.println("\n\nList reversed with procedural method");
list.print(list.head);
list.reverse(null, list.head);
System.out.println("\n\nList re-reversed with recursive method");
list.print(list.head);
}
}

class SinglyLinkedList {
Node head;

public void print(Node node) {
System.out.print(node);
if (node.next != null) {
System.out.print(" -> ");
print(node.next);
}
}

// procedural reverse
public void reverse() {
Node n3 = head;
Node n2 = null;
Node n1 = null;
while (n3 != null) {
n1 = n2;
n2 = n3;
n3 = n2.next;
n2.next = n1;
}
head = n2;
}

// recursive reverse
public void reverse(Node n1, Node n2) {
Node n3 = n2.next;
n2.next = n1;
if (n3 != null) {
reverse(n2, n3);
} else {
head = n2;
}
}
}

class Node {
Node next;
String value;

Node(String value) {
this.value = value;
}

public String toString() {
return value;
}

}

Stack Using LinkedList

Height of BinaryTree

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

LCA BinaryTree

Vertical Sum in a Binary Tree

https://gist.github.com/dheeraj9823/7200759

In Pre Post Order Non Recursive BinaryTree

DeleteNode BST

public class BST {

public static void main(String [] args)
{
treeNode a = new treeNode();
a.setData(4);
treeNode b = new treeNode();
b.setData(2);
treeNode c = new treeNode();
c.setData(6);
treeNode d = new treeNode();
d.setData(1);
treeNode e = new treeNode();
e.setData(3);
treeNode f = new treeNode();
f.setData(5);
treeNode g = new treeNode();
g.setData(7);

a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
c.setLeft(f);
c.setRight(g);
BST bst = new BST();
treeNode node = bst.findbstNonrec(a, 7);
System.out.print(node.getData());
treeNode del = bst.deleteNodeBST(a, 3);

}

public treeNode findbst(treeNode root,int data)
{
if(root == null)
return null;
if(data < root.getData())
return findbst(root.getLeft(), data);
if(data > root.getData())
return findbst(root.getRight(),data);
return root;

}

public treeNode findbstNonrec(treeNode root, int data)
{
if(root == null)
return null;
while(root != null)
{
if(data < root.getData())
root = root.getLeft();
else if(data > root.getData())
root = root.getRight();
else
return root;
}
return null;
}

public treeNode deleteNodeBST(treeNode root , int data)
{
treeNode temp;
treeNode left,right;

if(root == null)
System.out.println("Element not in the tree");
else if(data < root.getData())
root.setLeft(deleteNodeBST(root.getLeft(),data)) ;
else if(data > root.getData())
root.setRight(deleteNodeBST(root.getRight(),data)) ;

else
{
if(root.getLeft() != null && root.getRight() !=null)
{
temp = FindMax(root.getLeft());
root.setData(temp.getData());
root.setLeft(deleteNodeBST(root.getLeft(), root.getData()));
}
else
{
temp = root;
if(root.getLeft() == null)
{
root = root.getRight();
}
else if(root.getRight() == null)
{
root = root.getLeft();
}

}
}

return root;
}

private treeNode FindMax(treeNode root) {
// TODO Auto-generated method stub

if(root == null)
return null;
else
if(root.getRight() == null)
return root;
else
return FindMax(root.getRight());

}

}

ZigZag Traversal BinaryTree

Diameter Binary Tree

Stack using Array

public class Stack {

public int tos;
public int []stk;

public Stack(int size)
{
tos = -1;
stk = new int[size];
}
public void push(int data)
{
if(tos==stk.length-1)
{
System.out.println("Stack is Full");
}
else
{
stk[++tos] = data;
System.out.println(stk[tos]);
}
}

public int pop()
{
if(tos==-1)
{
System.out.println("Stack is Empty");
return 0;
}
else
{
return stk[tos--];

}
}

public static void main(String []args)
{
Stack s = new Stack(4);
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.pop());
}
}

Reverse k nodes in a linkedlist

public class ReverseKNodes {

public static void main(String[] args) {

lnode a = new lnode();
a.setData(1);
lnode b = new lnode();
b.setData(2);
lnode c = new lnode();
c.setData(3);
lnode d = new lnode();
d.setData(4);
lnode e = new lnode();
e.setData(5);
lnode f = new lnode();
f.setData(6);
lnode g = new lnode();
g.setData(7);
lnode h = new lnode();
h.setData(8);
lnode i = new lnode();
i.setData(9);
lnode j = new lnode();
j.setData(10);
lnode k = new lnode();
k.setData(11);
a.setNext(b);
b.setNext(c);
c.setNext(d);
d.setNext(e);
e.setNext(f);
f.setNext(g);
g.setNext(h);
h.setNext(i);
i.setNext(j);
j.setNext(k);

ReverseKNodes r = new ReverseKNodes();
lnode finalhead = r.ReverseKnodes(3, a);
while(finalhead != null)
{
System.out.println(finalhead.getData());
finalhead = finalhead.getNext();
}

}

public lnode ReverseKnodes(int K, lnode head)
{
int count=0;
lnode cur= head , newHead,temp=null,next=null,poc=null,fpoc= null;
if(HasKNodes(cur, K-1))
{
newHead = GetPlusOneNode(K-1, cur);

}
else
newHead = head;
while(cur!=null && HasKNodes(cur, K))
{

fpoc = poc;
temp = GetPlusOneNode(K, cur);
poc = cur;

int i=0;
while(i{

next = cur.getNext();
cur.setNext(temp);
temp = cur;
cur = next;
i++;
}
if(count != 0)
fpoc.setNext(temp);
count++;

}

return newHead;
}

public boolean HasKNodes(lnode head, int K) {

lnode node;
int i;
for(i=0;head != null && i <= K -1;i++,head = head.getNext());

if(i==K)
{
return true;
}
else
return false;
}

public lnode GetPlusOneNode(int K,lnode head)
{
int i;
lnode kth;
for(i=0,kth=head;kth!= null&& i<= K-1;i++,kth = kth.getNext());
if(i==K && kth != null)
{
return kth;
}

return head.getNext();
}

}

class lnode {
private int data;
private lnode next;

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public lnode getNext() {
return next;
}

public void setNext(lnode next) {
this.next = next;
}
}