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。但是，漏了考慮要是有重復值的話，就會被覆蓋了。只有像答案這樣，優先檢查是否有匹配值，有匹配值就馬上匹配就好。
新聞熱點
疑難解答
