Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space? 
Solution 1: reverse the list, if there is a circle, it will point back to head.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode curA = head;
        ListNode curB = curA.next;
        while (curB.next != null) {
            if (curB == head) return true; //cycle found
            if (curB.next != null) {
                ListNode curC = curB.next;
                curB.next = curA; // reverse A->B to B->A
                curA = curB;
                curB = curC;
            }
        }
        return false;
    }
}

Solution 2: traverse the list, if a node does not point to itself, then make it point to itself and process next node. If a node points to itself, then there must be a cycle.

public class Solution {
    public boolean hasCycle(ListNode head) {
        while(head != null && head.next != null) {
            ListNode tmp = head.next;
            head.next = head; //make the node point to itself
            head = tmp;
            if (head.next == head) return true;
        }
        return false;
    }   
}

Solution 3: fast runner and slow runner, won't change the list.

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;   
    }   
}

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i. 
Design an algorithm to find the maximum profit. You may complete at most two transactions. 
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        if (prices.length ==2 )
            return prices[0] < prices[1] ? prices[1] - prices[0] : 0;
            
        int[] maxProf1 = new int[prices.length];
        int maxPrice = prices[prices.length-1];
        maxProf1[maxProf1.length-1] = 0;
        
        for (int i = maxProf1.length-2; i >=0; i--) {
            int profit1;
            if (prices[i] > maxPrice) {
                profit1 = 0;
                maxPrice = prices[i];
            }
            else {
                profit1 = maxPrice - prices[i];
            }
            maxProf1[i] = profit1 > maxProf1[i+1] ? profit1 : maxProf1[i+1];
        }
        
        int minPrice = prices[0];
        int maxProf2 = 0;
        int maxProf = 0;
        for (int j = 0; j < prices.length-2; j++) {
            int profit2;
            if (prices[j] > minPrice) {
                profit2 = prices[j] - minPrice;
            }
            else {
                profit2 = 0;
                minPrice = prices[j];
            }
            maxProf2 = maxProf2 > profit2 ? maxProf2 : profit2;
            int profit = maxProf2 + maxProf1[j];
            maxProf = maxProf > profit ? maxProf : profit;
        }
        
        return maxProf;
    }
}

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i. 
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution1: straight forward, buy at the low price before it goes up and sell at the high price before it goes down.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        if (prices.length == 2)
            return prices[0] > prices[1] ? 0 : prices[1] - prices[0];
        
        int low = 0;  
        int high = 0;
        int ans = 0;
        boolean hold = false;
        for (int i = 0; i < prices.length - 1; i++) {
            if (!hold && prices[i] < prices[i+1]) {
                hold = true;
                low = prices[i];
                continue;
            } 
            if (hold && prices[i] > prices[i+1]) {
                hold = false;
                high = prices[i];
                ans += high - low;
            }
        }
        
        if (hold)
            ans += prices[prices.length-1] - low;
        return ans;
    }
}

Solution2: more mathematical way, add every increment

public class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length - 1; i++)
            ans += (prices[i+1] > prices[i] ? prices[i+1] - prices[i] : 0);
       
        return ans;
    }
}

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i. 
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Solution1:

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        if (prices.length == 2)
            return prices[0] > prices[1] ? 0 : prices[1] - prices[0];
        
        int[] maxAfter = new int[prices.length-1];
        maxAfter[maxAfter.length-1] = prices[prices.length-1];
        
        for (int j = maxAfter.length - 2; j >= 0; j--)
            maxAfter[j] = maxAfter[j+1] > prices[j+1] ? maxAfter[j+1] : prices[j+1];

        int ans = 0;
        for (int i = 0; i < maxAfter.length; i++)
            ans = (maxAfter[i] - prices[i]) > ans ? (maxAfter[i] - prices[i]) : ans;
        return ans;
    }
}

Solution2: improved from solution1, space efficient

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        
        int maxAfter = prices[prices.length-1];
        int maxProf = 0;
        
        for (int j = prices.length - 2; j >= 0; j--) {
            if (prices[j] < maxAfter) {
                int profit = maxAfter - prices[j];
            
                maxProf = profit > maxProf ? profit : maxProf;
            } 
            else 
                maxAfter = prices[j];
        }
        return maxProf;
    }
}

Single Number

Given an array of integers, every element appears twice except for one. Find that single one. 
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        int res = 0;
        for(int i = 0; i < A.length; i++) {
            res = res^A[i];
        }
        return res;
    }
}

Reverse Integer

Reverse digits of an integer. 
Example1: x = 123, return 321 
Example2: x = -123, return -321

public class Solution {
    public int reverse(int x) {
       int positive = Math.abs(x);
       int res = 0;
       while(positive>0) {
           res = res *10 + positive % 10;
           positive = positive/10;
       }
       return x>=0? res: -res;
    }
}

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        return maxDep(root, 0);
    }
    
    public int maxDep(TreeNode node, int dep) {
        if (node == null) return dep;
        TreeNode rTree = node.left;
        TreeNode lTree = node.right;
        if (rTree == null && lTree == null) return dep+1;
        if (rTree == null)
            return maxDep(lTree, dep+1);
        if (lTree == null)
            return maxDep(rTree, dep+1);
        int ldep = maxDep(lTree, dep+1);
        int rdep = maxDep(rTree, dep+1);
        return (ldep > rdep) ? ldep : rdep;
        
    }
}