Binary Tree Preorder Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
       
        preorder(root, result);
       
        return result;
    }
   
    private void preorder(TreeNode node, List<Integer> list)
    {
        if (node == null) return;
       
        list.add(node.val);
        preorder(node.left, list);
        preorder(node.right, list);
    }
}

Linked List Cycle

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head==null || head.next==null) return false;
     
        ListNode current = head;
        ListNode pivot = current;
     
        if (pivot.next == null) return false;
     
        do
        {
            pivot = pivot.next;
            pivot = pivot.next;
            current = current.next;
        } while(pivot != null && pivot.next != null && pivot.next != current && pivot != current);
     
        if ( pivot != null && (pivot.next == current || pivot == current)) return true;
        return false;
    }
}

Palindrome Number

----Note: negative number is not Palindrome
public class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
        return false;
        }
       
        String value = String.valueOf(x);
       
        for(int i=0; i<value.length()/2; i++){
        if(value.charAt(i)!=value.charAt(value.length()-i-1)) return false;
        }
       
        return true;
    }
}

Evaluate Reverse Polish Notation

public int evalRPN(String[] tokens){
int invalidResult = 0;
int size = tokens.length;

//validate tokens:
for(int i=0; i<size; i++){
if(!isInteger(tokens[i]) && !isSymbol(tokens[i])){
return invalidResult;
}
}

if(size==1 && isInteger(tokens[0])) return getInteger(tokens[0]);

if (size<2) return invalidResult;

Deque<Integer> numQ=new ArrayDeque<Integer>();
numQ.addFirst(getInteger(tokens[0]));
numQ.addFirst(getInteger(tokens[1]));
int idx = 2;
int op1;
int op2;
while(idx<tokens.length && numQ.size()>0){
if (isSymbol(tokens[idx])){
op2 = numQ.remove();
op1 = numQ.remove();
numQ.addFirst(calculate(op1, op2, tokens[idx]));
}
else {
numQ.addFirst(getInteger(tokens[idx]));
}
idx++;
}
if(numQ.size()!=1 || idx!=tokens.length) return invalidResult;
return numQ.remove();
}

private boolean isSymbol(String s){
if (s.equalsIgnoreCase("+")
||s.equalsIgnoreCase("-")
||s.equalsIgnoreCase("*")
||s.equalsIgnoreCase("/")) return true;
return false;
}

private int calculate(int op1, int op2, String op){
if(op.equalsIgnoreCase("+")){
return op1 + op2;
}
if(op.equalsIgnoreCase("-")){
return op1 - op2;
}
if(op.equalsIgnoreCase("*")){
return op1 * op2;
}
if(op.equalsIgnoreCase("/")){
if (op2 == 0) return 0;
return op1 / op2;
}
return 0;
}

private boolean isInteger(String s){
return s.matches("\\d++") || s.matches("\\+\\d++") || s.matches("-\\d++");
}

private int getInteger(String s){
int invalidValue = 0;
if (s.matches("\\d++")) return Integer.valueOf(s);
if (s.matches("\\+\\d++"))return Integer.valueOf(s.substring(1));
if (s.matches("-\\d++")) return Integer.valueOf(s.substring(1))*(-1);
return invalidValue;
}
}

Reverse Words in a String

/*non optimized version*/
public class Solution {
public String reverseWords(String s){
   if(s.isEmpty() || s.length() < 2){
return s;
}
     
String newString = "";
while(!s.isEmpty() && s.charAt(0)==' '){
s=s.substring(1);
}

while(!s.isEmpty() && s.charAt(s.length()-1)==' '){
s=s.substring(0,s.length()-1);
}

if(s.isEmpty()){
return newString;
}

String reversedChars = reverseLetters(s);
String[] stringArray = reversedChars.split(" ++");
String temp;
for(int i=0; i<stringArray.length; i++){
   temp = reverseLetters(stringArray[i]);
if (!temp.isEmpty()){
   newString = newString + temp;
   if (i!=stringArray.length-1){
newString = newString + " ";
}
}
}

return newString;
}

private String reverseLetters(String s){
int length = s.length();
if (s.isEmpty() || length < 2){
return s;
}

String newString = "";
int idx=length-1;
newString = newString + s.substring(idx);
idx--;
while(idx>=0){
newString = newString + s.substring(idx,idx+1);
idx--;
}

return newString;
}
}

---optimized:
public class Solution {
public int evalRPN(String[] tokens){
int invalidResult = 0;
int size = tokens.length;

if(size==1 && isInteger(tokens[0])) return getInteger(tokens[0]);

if (size<2) return invalidResult;

Deque<Integer> numQ=new ArrayDeque<Integer>();
numQ.addFirst(getInteger(tokens[0]));
numQ.addFirst(getInteger(tokens[1]));
int idx = 2;
int op1;
int op2;
while(idx<tokens.length && numQ.size()>0){
   if(!isInteger(tokens[idx]) && !isSymbol(tokens[idx])){
return invalidResult;
}
if (isSymbol(tokens[idx])){
op2 = numQ.remove();
op1 = numQ.remove();
numQ.addFirst(calculate(op1, op2, tokens[idx]));
}
else {
numQ.addFirst(getInteger(tokens[idx]));
}
idx++;
}
if(numQ.size()!=1 || idx!=tokens.length) return invalidResult;
return numQ.remove();
}

private boolean isSymbol(String s){
if (s.equalsIgnoreCase("+")
||s.equalsIgnoreCase("-")
||s.equalsIgnoreCase("*")
||s.equalsIgnoreCase("/")) return true;
return false;
}

private int calculate(int op1, int op2, String op){
if(op.equalsIgnoreCase("+")){
return op1 + op2;
}
if(op.equalsIgnoreCase("-")){
return op1 - op2;
}
if(op.equalsIgnoreCase("*")){
return op1 * op2;
}
if(op.equalsIgnoreCase("/")){
if (op2 == 0) return 0;
return op1 / op2;
}
return 0;
}

private boolean isInteger(String s){
return s.matches("\\d++") || s.matches("\\+\\d++") || s.matches("-\\d++");
}

private int getInteger(String s){
int invalidValue = 0;
if (s.matches("\\d++")) return Integer.valueOf(s);
if (s.matches("\\+\\d++"))return Integer.valueOf(s.substring(1));
if (s.matches("-\\d++")) return Integer.valueOf(s.substring(1))*(-1);
return invalidValue;
}
}