WOLOHAHA

package POJ;

import java.util.ArrayList;
import java.util.Stack;


public class Main{

	/**
	 * 

WOLOHAHA

public class Main{

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		StackWithMin stack=new StackWithMin();
		stack.push(2);
		System.out.println(stack.min());
		System.out.println("stack.minStack.size()===="+stack.minStack.size());
		stack.push(1);
		System.out.println(stack.min());

WOLOHAHA

public class Main {

	/**
	 * 3.1 Describe how you could use a single array to implement three stacks.
	 * 
	 * Solution:
	 * this part we could implement three stacks dynamically.
	 * the challenge here is that we need to keep track of the top and all available space.
	 * this can be done by using a Node structure holding the val and the former Node and a queue of empty cells
	 * 

WOLOHAHA

public class Main {

	/**
	 * 2.7 Implement a function to check if a linked list is a palindrome.
	 * 
	 * Solution:
	 * find the middle of the list. Instead of creating a stack, use recursion
	 * to solve it. We will need a wrapper class though. Pass the head of the
	 * list in the function. When we meet the last node in the list in the
	 * recursion, compare it with the head. If they are the same, return

WOLOHAHA

/**
 * 2.6 Given a circular linked list, implement an algorithm which
 * returns the node at the beginning of the loop.
 * DEFINITION
 * Circular linked list: A (corrupt) linked list in which a node's
 * next pointer points to an earlier node, so as to make a loop in
 * the linked list.
 * EXAMPLE
 * Input:A ->B->C->D->E-> C
 * Output:C

WOLOHAHA

public class Main {

	/**
	 * 2.5 
	 *  
	 * FOLLOW UP
	 * Suppose the digits are stored in forward order. Repeat the above problem. 
	 * 
	 * EXAMPLE
	 * Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).That is,617 + 295.

WOLOHAHA

/**
 * 2.5 You have two numbers represented by a linked list, where each node contains
 * a single digit. The digits are stored in reverse order, such that the Ts digit is
 * at the head of the list. Write a function that adds the two numbers and returns
 * the sum as a linked list.
 * 
 * EXAMPLE
 * Input:(7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295.
 * Output: 2 -> 1 -> 9.That is, 912.
 * 

WOLOHAHA

public class Main {

	/**
	 * 2.4 Write code to partition a linked list around a value x, such that 
	 * all nodes less than x come before all nodes greater than or equal to x.
	 * 
	 * @Runtime & spaces
	 * runtime: O(n)
	 * space:   O(1)
	 */

WOLOHAHA

/**
 * 2.3 Implement an algorithm to delete a node in the middle of a singly
 * linked list, given only access to that node. 
 * EXAMPLE
 * Input: the node c from the linked list a->b->c->d->e
 * Result: nothing is returned, but the new linked list looks like a- >b- >d->e
 * 
 * 
 * @Runtime & spaces
 * runtime: O(1)

WOLOHAHA

public class Main {

	/**
	 * 2.2 Implement an algorithm to find the k th
	 * to last element of a singly linked list.
	 * 
	 * we have defined k such that passing in k = 1 would return
	 * the last element,k = 2 would return to the second to last
	 * element,and soon.It is equally acceptable to define k such
	 * that k = 0 would return the last element.