Merge k Sorted Lists (这题是用PQ，或者merge sort都可以做，关于第K大的问题，参考: Find Kth 题目类型总结)
Sort an Array (重点掌握merge sort和quick sort，因为两者可以演变为,divide conquer, quick select, 参考: Find Kth 题目类型总结)
Sort Colors 思路：三指针，i, j, k. 目标是 0 ，1 ，2 用i来保持0的位置，k来保持2的位置，j来做扫描运动，如果j遇见0，换到前面去，如果遇见2换到后面去。注意，如果换到前面的情况，i可以++，j也可以++，因为换回来的只可能是1，不可能是别的情况，因为前面的i部分已经被扫描过，2已经到后面去了。j遇见2，与后面进行互换的时候，j不能++，因为不知道换回来的是0，还是1，还是2，还得进行一次判断。这也是这个题目的考点。
Quick Select 题型参考: Find Kth 题目类型总结
Kth Smallest Numbers in Unsorted Array quick select的标准模板，一定要熟记，多写几次就熟悉了。
public class Solution { /** * @param k: An integer * @param nums: An integer array * @return: kth smallest element */ public int kthSmallest(int k, int[] nums) { if(nums == null || nums.length == 0) { return -1; } return findKth(nums, 0, nums.length - 1, k); } private int findKth(int[] A, int start, int end, int k) { if(start == end) { return A[start]; } int mid = start + (end - start) / 2; int pivot = A[mid]; int i = start, j = end; while(i <= j) { while(i <= j && A[i] < pivot) { i++; } while(i <= j && A[j] > pivot) { j--; } if(i <= j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } if(start + k - 1 <= j) { return findKth(A, start, j, k); } if(start + k - 1 >= i) { return findKth(A, i, end, k - (i - start)); } return A[j + 1]; } }Sort List 思路：merge sort Linked List, jame bone,找到middle point的前一个，然后把list 劈开；
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode slow = findMiddle(head); ListNode newhead = slow.next; slow.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(newhead); return merge(l1, l2); } private ListNode findMiddle(ListNode head) { ListNode dummpy = new ListNode(-1); dummpy.next = head; ListNode slow = dummpy; ListNode fast = dummpy; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummpy = new ListNode(-1); ListNode cur = dummpy; while(l1 != null && l2 != null) { if(l1.val < l2.val) { cur.next = l1; l1 = l1.next; cur = cur.next; } else { cur.next = l2; l2 = l2.next; cur = cur.next; } } if(l1 != null) { cur.next = l1; } if(l2 != null) { cur.next = l2; } return dummpy.next; } }Merge Intervals (Interval 是一类很重要的题目，往往跟Sweep line相结合, 参考: 扫描线Sweep Line算法总结)
思路：首先按照start sort之后，判断end是否跟start相交，如果相交，end就是两者最大值；否则加入cur；注意最后需要加入cur；
Convert Sorted Array to Binary Search Tree 思路：找中间点，就是root，然后两边分别构造左子树和右子树。
Convert Sorted List to Binary Search Tree 思路：jame bond 的思路，找mid的前一个点，然后两边分开找；这里只传递一个参数；注意middle的前后都要断开，否则会死循环；
Search in Rotated Sorted Array 思路：按照九章的模板来写；总体思想就是：确定哪段是升序的，然后把target钳住里面，判断是否在里面，否则搜另外一边；因为array是rotated，所以，只能是两边要么一边升序，把target放在升序的序列里面进行判断，如果不在，选另外一边；
关于search，这里有Binary Search 总结
