Week2-2016

linked-list-cycle.java

public boolean hasCycle(ListNode head) {
    if(head==null){
        return false;
    }
    ListNode slow = head;
    ListNode fast = head;
    
    while(fast!=null&&fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
        if(slow==fast){//collision point
          // I didn't know you could compare nodes directly, I thought you could only compare their values, prior to reading CTCI
            return true;
        }
    }
    return false;
    
}

linked-list-cycle2.java

public ListNode detectCycle(ListNode head) {
        if(head==null){
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    
    while(fast!=null&&fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
        if(slow==fast){//collision point
        // I didn't know you could compare nodes directly, I thought you could only compare their values
            break;
        }
    }
        if(fast==null||fast.next==null){
        return null;
    }
    slow=head;
    
    while(slow!=fast){
        slow=slow.next;
        fast=fast.next;
    }
    return fast;
    }

MyStack.java

public class MyStack<T extends Comparable<T>>{

	private static class StackNode<T extends Comparable<T>> {
		private Comparable<T> data;
		private StackNode<T> next;

		public StackNode(Comparable<T> item){
			this.data =item;
		}

	} 
	private MinStack<T> minStack;
	private StackNode<T> top;

	public void push(Comparable<T> item){
		StackNode<T> t = new StackNode(item);
		t.next =top;
		top= t;
		minStack.push(item);
	}

	public void pop(){
		if (top==null){
			throw new EmptyStackException();
		}
		top=top.next;
		minStack.top=minStack.top.next;
	}

	public StackNode min(){
		return minStack.top;
	}

	public class MinStack<T extends Comparable<T>> extends MyStack<T> {

		private StackNode<T> top;
		@Override
		public void push(Comparable<T> item){
			StackNode t = new StackNode(item);
			if(top==null){
				top=t; return;
			}
			if (t.data.compareTo(top.data)>0){//if insert is larger than top
				t.data=top.data;
			}
			t.next=top;
			top=t;
		}

	}

}

valid-parens.java

public boolean isValid(String s) {
	    char [] arr = s.toCharArray();
	    HashMap<Character,Character> map = new HashMap<Character,Character>();
	    Stack<Character> stack = new Stack<Character>();
	    map.put('(', ')');
	    map.put('{', '}');
	    map.put('[', ']');
	    int i =0;
	    while (i<arr.length){
	    	if(map.containsKey(arr[i])){
	    		stack.push(arr[i]);
	    	}
	    	else{
	    		if(!stack.empty() && map.get(stack.peek())==arr[i]){
	    			stack.pop();
	    		}
	    		else{
	    			return false;
	    		}
	    	}
	    	i++;
	    }
		if(stack.isEmpty()){
			return true;
		}
		else{
			return false;
		}
	}