1、（206）. Reverse Linked List

Reverse a singly linked list.

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) {            return head;        }                ListNode cur = head;        ListNode PRev = null;        ListNode tmp = null;                while (cur != null) {            tmp = cur.next;            cur.next = prev;            prev = cur;            cur = tmp;        }                return prev;    }}
凡是涉及到交換，一般都要涉及到新建一個臨時的第三方變量。
2、（ 445）. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.Follow up:What if you cannot modify the input lists? In other Words, reversing the lists is not allowed.Example:Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7
方法一：利用鏈表轉置和鏈表合并求和（鏈表合并的基礎上求和）
/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */  /**  * Way 1: Use reverse LinkedList  */public class Solution {    private ListNode reverseLList(ListNode head) {        if (head == null || head.next == null) {            return head;        }                ListNode cur = head;        ListNode prev = null;        ListNode tmp = null;                while (cur != null) {            tmp = cur.next;            cur.next = prev;            prev = cur;            cur = tmp;        }        return prev;    }        private ListNode mergeSum(ListNode l1, ListNode l2) {        ListNode dummy = new ListNode(-1);        ListNode backup = dummy;        int overflow = 0;        int tmpSum = 0;                while (l1 != null && l2 != null) {            tmpSum = l1.val + l2.val + overflow;            if (tmpSum >= 10) {                overflow = 1;                tmpSum = tmpSum % 10;            } else {                overflow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l1 = l1.next;            l2 = l2.next;        }                while (l1 != null) {            tmpSum = l1.val + overflow;            if (tmpSum >= 10) {                overflow = 1;                tmpSum = tmpSum % 10;            } else {                overflow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l1 = l1.next;        }                while (l2 != null) {            tmpSum = l2.val + overflow;            if (tmpSum >= 10) {                overflow = 1;                tmpSum = tmpSum % 10;            } else {                overflow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l2 = l2.next;        }                if (overflow != 0) {//錯誤1            dummy.next = new ListNode(overflow);            dummy = dummy.next;        }                return backup.next;    }    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode headL1 = reverseLList(l1);        ListNode headL2 = reverseLList(l2);                ListNode ans = mergeSum(headL1, headL2);                ans = reverseLList(ans);                return ans;    }}
這題犯的錯誤在于：忘了考慮兩個相等位數的數相加要是有進位的時候，要把進位放進結果里。
方法二：不實際轉置鏈表，利用stack來實現轉置。寫這個程序時，犯了兩個錯誤：1） LinkedList實現stack的時候，注意如果直接使用removeLast()的方法時，當LinkedList為空，會直接返回NoSuchElement 的run time exception，而使用peekLast() 則只會返回空。另外，可以使用isEmpty()來檢查是否為空。2）StackReverse是為了產生一個新的鏈表，當你產生一個新的鏈表時，需要構建的每一個都要構造一個新的節點，不能連接到舊的節點。（Deep Copy那題也犯了這個錯誤）
/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    private ListNode stackReverse (ListNode head) {        LinkedList<ListNode> stack = new LinkedList<ListNode>();        ListNode dummy = new ListNode(-1);        ListNode backupDummy = dummy;        ListNode tmp = null;                //put all the listnode into the stack        while (head != null) {            stack.addLast(head);            head = head.next;        }                //pop all the listnode and construct a new linkedlist        while (!(stack.isEmpty())) {//注意補充下API的知識            tmp = stack.removeLast();            dummy.next = new ListNode(tmp.val);            dummy = dummy.next;        }                return backupDummy.next;    }        private ListNode mergeSum(ListNode l1, ListNode l2) {        int tmpSum = 0;        int overFlow = 0;                ListNode dummy = new ListNode(-1);        ListNode backupDummy = dummy;                while (l1 != null && l2 != null) {            tmpSum = l1.val + l2.val + overFlow;            if (tmpSum >= 10) {                overFlow = 1;                tmpSum = tmpSum % 10;            } else {                overFlow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l1 = l1.next;            l2 = l2.next;        }                while (l1 != null) {            tmpSum = l1.val + overFlow;            if (tmpSum >= 10) {                overFlow = 1;                tmpSum = tmpSum % 10;            } else {                overFlow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l1 = l1.next;        }                while (l2 != null) {            tmpSum = l2.val + overFlow;            if (tmpSum >= 10) {                overFlow = 1;                tmpSum = tmpSum % 10;            } else {                overFlow = 0;            }            dummy.next = new ListNode(tmpSum);            dummy = dummy.next;            l2 = l2.next;        }                //do not forget the overflow        if (overFlow != 0) {            dummy.next = new ListNode(overFlow);            overFlow = 0;            dummy = dummy.next;        }                return backupDummy.next;    }        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode newListOne = stackReverse(l1);        ListNode newListTwo = stackReverse(l2);                ListNode ans = mergeSum(newListOne, newListTwo);                ListNode answer = stackReverse(ans);                return answer;    }}
3/  （138.）Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.
這道題有兩種方法，具體的可以參考刷題題庫1.這里作簡略描述：
方法一：使用hashtable，遍歷整個鏈表，把每個節點的新節點（注意不是random節點，這里想錯了）存在hashtable，同時創建一個沒有random pointer但其余一樣的鏈表。然后第二遍再通過hashtable連接random pointer。（注意，是新建的random節點，不是舊的節點。）
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { *     int label; *     RandomListNode next, random; *     RandomListNode(int x) { this.label = x; } * }; */public class Solution {    public RandomListNode copyRandomList(RandomListNode head) {        if (head == null) {            return null;        }                HashMap<RandomListNode, RandomListNode> nodeNewNode = new HashMap<RandomListNode, RandomListNode>();        RandomListNode cur = head;        RandomListNode dummy = new RandomListNode(-1); // new linkedlist's dummy        RandomListNode backDummy = dummy;        RandomListNode tmp = null;                while (cur != null) {            tmp = new RandomListNode(cur.label);            dummy.next = tmp;            nodeNewNode.put(cur,tmp);            cur = cur.next;            dummy = dummy.next;        }                // scan the new linked list and write the random pointers        cur = head;        RandomListNode newHead = backDummy.next;        while (cur != null && newHead != null) {            RandomListNode randomTmp = nodeNewNode.get(cur.random);            newHead.random = randomTmp;            cur = cur.next;            newHead = newHead.next;        }                return backDummy.next;    }}
方法二：Follow up的題目如果是想利用空間復雜度為O(1)的方法實現呢？這時候就要巧妙一點了。具體的圖可以參考鏈接：http://blog.csdn.net/firehotest/article/details/52665467。簡而言之，就是先把復制的節點放在原節點后面，然后再掃一遍的時候，復制random域和斷開多余的鏈接。(明天寫這個版本)
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { *     int label; *     RandomListNode next, random; *     RandomListNode(int x) { this.label = x; } * }; */public class Solution {    public RandomListNode copyRandomList(RandomListNode head) {        if (head == null) {            return null;        }                RandomListNode tmp = null;        RandomListNode cur = head;        RandomListNode prev = null;                while (cur != null) {            prev = cur;            cur = cur.next;                        tmp = new RandomListNode(prev.label);            tmp.next = cur;            prev.next = tmp;        }                //connect the random fields        cur = head.next;        prev = head;        tmp = cur;                while (cur != null) {            if (prev.random != null) {                cur.random = prev.random.next;            } else {                cur.random = null;            }                                    if (cur.next == null) {                break;            }            prev = prev.next.next;            cur = cur.next.next;        }                cur = head.next;        prev = head;                //disconnect the copy and origin        while (cur != null) {            prev.next = cur.next;            if (cur.next != null) {                cur.next = cur.next.next;            } else {                cur.next = null;                break;            }            prev = prev.next;            cur = cur.next;        }                return tmp;    }}
4/ （121.） Best Time to Buy and Sell Stock
這道題的做法參考插入排序的做法，設立一個變量作為臨時的結果變量，不斷更新，直到遍歷完整個數組。在這里的臨時結果變量有哪些呢？想要獲得最大的profit，必須是以當前的或者之后的價格減去目前已有的最小價格。
所以這道題應該這么做：
public class Solution {    public int maxProfit(int[] prices) {        if (prices == null || prices.length == 0) {            return 0;        }                int profit = 0;        int minPrice = prices[0];                for (int i = 0; i < prices.length; i++) {            if (prices[i] < minPrice) {                minPrice = prices[i];            }            for (int j = i + 1; j < prices.length; j++) {                profit = Math.max(profit, prices[j] - minPrice);            }        }                return profit;    }}但這個算法其實不用寫兩個循環，可以用一個算法解決：
public class Solution {    public int maxProfit(int[] prices) {        if (prices == null || prices.length == 0) {            return 0;        }                int minPrice = prices[0];        int profit = 0;                for (int tmp : prices) {            if (tmp < minPrice) {                minPrice = tmp;            }                        profit = Math.max(profit, tmp - minPrice);        }                return profit;    }}之前還寫過一個算法，實現把每一個時間點買入的最大profit求出來，更新最大的profit即可。但還是上述的方法最簡單。
5/ （283.） Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].Note:You must do this in-place without making a copy of the array.Minimize the total number of Operations.
其實這道題的思路也十分簡單，利用移位復制的方法，這個方法稱為insertion index. 
public class Solution {    public void moveZeroes(int[] nums) {        int index = 0;        int n = 0;                while (n < nums.length) {            if (nums[n] != 0) {                nums[index++] = nums[n];            }            n = n + 1;        }                while (index < nums.length) {            nums[index++] = 0;        }    }}
6/ （1.） Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
public class Solution {    public int[] twoSum(int[] nums, int target) {        if (nums == null || nums.length < 2) {            return null;        }                HashMap<Integer, Integer> valIndex = new HashMap<Integer, Integer>();        for (int i = 0; i < nums.length; i++) {            if (valIndex.containsKey(target - nums[i])) {                return new int[]{i,valIndex.get(target - nums[i])};            } else {                valIndex.put(nums[i],i);            }        }        return new int[2];    }}
這題犯的錯是，一開始打算把所有的值當做key，然后存在index作為value。但是，漏了考慮要是有重復值的話，就會被覆蓋了。只有像答案這樣，優先檢查是否有匹配值，有匹配值就馬上匹配就好。