LeetCode笔记

1.Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

　　该题可以使用中间间隔固定长度的两个指针，同时行走，当前方指针到达尾部，后面的指针也就到达了指定地点，进行删除才操作即可。

初始版本：

 1     public ListNode removeNthFromEnd(ListNode head, int n) {
 2         if (n <= 0||head == null) {
 3             return null;
 4         }
 5         ListNode nth = head;
 6         ListNode des = head;
 7         for(int i = 0;i < n;i++){
 8             if (des == null) {
 9                 return null;
10             }
11             des = des.next;
12         }
13         while(des.next!= null){
14             nth = nth.next;
15             des = des.next;
16         }
17         
18         nth.next = nth.next.next;
19         
20         return head;
21         
22     }

　　在本地自己定义了一个singleLinkedList，作为参数传进函数中，本地运行正确，可是在OJ上死活就是java.lang.NullPointerException，无奈一步步提交就是各种错误，而本地运行完全正确。后来照着答案一步步找原因才发现，当输入数据为{1}，1或者{1,2}，2时非常容易出现空指针的情况。因此无论如何，链表中保持有一个头指针（空指针，beginMaker）是一个非常明智的选择，将即使是一个数据也能像一般情况一样不容易出现错误。

修改后版本：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode removeNthFromEnd(ListNode head, int n) { //0,length,length+为特殊情况
14         if (n <= 0||head == null) {    //n取0
15             return null;
16         }
17         ListNode tmp = new ListNode(0);    //注意添加头指针，这是一个非常良好的习惯，上文有讲不加的后果
18         tmp.next = head;
19         ListNode nth = tmp;
20         ListNode des = head;
21 
22         for(int i = 0;i < n;i++){
23             if (des == null) {    //当n取length+时
24                 return null;
25             }
26             des = des.next;    //因为此时不知道n的长度，当n取length的时候des就是null
27         }
28         while(des != null){    //呼应n取length时，因此最好不要用des.next!=null
29             nth = nth.next;
30             des = des.next;
31         }
32         
33         nth.next = nth.next.next;
34 
35         return tmp.next;
36         
37     }
38 }

2.Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

　　此题仍旧可用上题的思路，两个指针并排走，但是该题要注意一点就是当n取length+时候的情况，此时应该等同于对n取余（因为可以看做先由右转换几倍的n次，再右转换n%length次）。

　　因此特殊情况就是n取0（跟1~n-1的效果一样，其实不特殊），length（取余即，n%=length,此时n取0），length+（取余n%=length之后n取1~n-1）。仍旧注意添加头指针，一个非常良好的习惯。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     private int getLength(ListNode head){
14         int length = 0;
15         while(head != null){
16             length++;
17             head = head.next;
18         }
19         return length;
20         
21     }
22     public ListNode rotateRight(ListNode head, int n) {
23         if(n < 0||head == null) 
24             return null;
25         else
26             n %= getLength(head);
27         
28         ListNode beginner = new ListNode(0);
29         beginner.next = head;
30         ListNode p = beginner;
31         ListNode q = beginner;
32         for(int i = 0;i < n;i++){
33             q = q.next;    
34         }
35         while(q.next!=null){
36             p = p.next;
37             q = q.next;
38         }
39         
40         q.next = head;
41         head = p.next;
42         p.next = null;
43         
44         return head;
45         
46     }
47 }

View Code

3.Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

　　私以为这题出的有点贱，你要说是一般的二叉树，就地弄成链表也成；或者你说成一般二叉树就地排成有序链表也成；再或者你就直白点说前序有序二叉树就地排成列表也行。这么整考的不是解题能力考的是语文理解能力！！！喵喵咪，是程序猿语文不好，还是我等语文不好的注定要吃亏！！妹啊~

　　没想到都没用到debug就居然过了，太早增加我信心了，哈哈哈

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public void flatten(TreeNode root) {
12         if(root != null){
13         // 处理该节点的左子树，嵌入到该节点与该节点右子树之间
14             if(root.left != null){
15                 TreeNode marker = root.left;
16                 flatten(root.left);
17                 while(marker.right != null){
18                     marker = marker.right;
19                 }
20                 //嵌入操作
21                 marker.right = root.right;
22                 root.right =root.left;
23                 root.left = null;
24             }
25             //处理右子树
26             flatten(root.right);
27         }
28     }
29 }

View Code

　Program Creek上找到的非递归方法

 1 public class Solution {
 2     public void flatten(TreeNode root) {
 3         Stack<TreeNode> stack = new Stack<TreeNode>();
 4         TreeNode p = root;
 5  
 6         while(p != null || !stack.empty()){
 7  
 8             if(p.right != null){
 9                 stack.push(p.right);
10             }
11  
12             if(p.left != null){
13                 p.right = p.left;
14                 p.left = null;
15             }else if(!stack.empty()){
16                 TreeNode temp = stack.pop();
17                 p.right=temp;
18             }
19  
20             p = p.right;
21         }
22     }
23 }

4.Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

个人解法：

 1 public class Solution {
 2     public int removeElement(int[] A, int elem) {
 3         int marker = A.length -1;
 4         if(marker<0)
 5             return 0;
 6         else{
 7             for(int i = 0;i <= marker;i++){    //还是用while比较好，循环好控制
 8                 if(elem == A[i]){
 9                     while(A[marker] == elem){
10                         marker--;
11                         if(marker < i) return marker + 1;
12                     }
13                     A[i] = A[marker];
14                     marker--;
15                 }
16             }
17        }
18         return marker + 1;
19     }
20 }

更简洁的一种算法：

public class Solution {
    public int removeElement(int[] A, int elem) {
        int i = 0;
        int pointer = A.length - 1;
        while(i <= pointer){
            if(A[i] == elem){
                A[i] = A[pointer];    //无论A[pointer]是否等于elem都赋给，由于i此时并不自加，下次循环依旧判断
                pointer--;
            } else {    //这个地方处理的很好，只有i位置上的数被换了不等于elem的才检查下一个
                i++;
            }
        }
        return pointer + 1;
    }
}

5.Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

　　此题注意不要添加头结点，因为头结点的数据域不是实际的数据，它只起到节点的作用，而其数据会跟后面链表的数据冲突，影响链表数据判断。

 1 public class Solution {
 2     public ListNode deleteDuplicates(ListNode head) {
 3         if(head == null)
 4             return null;
 5         ListNode marker = head;
 6         while(marker.next != null){
 7             if(marker.val != marker.next.val){
 8                 marker =marker.next;
 9             }
10             else{
11                 marker.next = marker.next.next;
12             }
13         }
14         return head;
15     }
16 }

　　空间节省的一种解法，只使用一个指针marker，通过marker与marker.next的比对即可。476ms

　　相应的，使用两个指针p，q虽然多使用了一个空间，但是可以减少过多的删除操作。516ms

 1 public class Solution {
 2     public ListNode deleteDuplicates(ListNode head) {
 3         if(head == null)
 4             return null;
 5         ListNode p = head;
 6         ListNode q = head.next;
 7         while(q != null){
 8             if(p.val != q.val){
 9                 p.next = q;
10                 p = q;
11             }
12                 q = q.next;
13         }
14         p.next = null;
15         return head;
16     }
17 }

6.Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int p = 0;
        int q = 0;
        while(q<=A.length-1){            
            if(A[p]!=A[q]){
                p++;
                A[p]=A[q];
            }
            q++;
        }
        return p+1;
    }
}

7.Remove Duplicates from Sorted List II

Total Accepted: 20125 Total Submissions: 80878

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

　　本人的思路是添加一个比第一个数字还小（head.val-1）的头结点（在返回时候可删除），这样可形成一个三格，如下图。

　　在此三格中从第二个格开始检验，如果三格满足head.val<head.next.vall<head.next.next.val关系，则说明第二个格合格（没有其他数与第二格数相同），使用psv（保留到链表的操作指针）操作即可。如果有任何有重复的数字出现，那么就会有两个相同的数字进入"三格"中，即不满足以上关系，递推head指针随着格子移动继续处理。

　　被检验的数据是从第二格开始的，因此要添加头结点使真正的第一个数据处于第二格位置被检验，否则，会从第二个数据开始检验，无故丢失第一个数据。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode deleteDuplicates(ListNode head) {
14         if(head==null)  return null;//0
15         ListNode dummy = new ListNode(head.val-1);
16         dummy.next = head;
17         ListNode psv= dummy;
18         head = dummy;
19         
20         while(head.next.next!=null){
21             if(head.val<head.next.val&&head.next.val<head.next.next.val){
22                 psv.next = head.next;
23                 head = head.next;
24                 psv = head;
25             }else
26             head=head.next;
27         }
28         
29         if(head.val<head.next.val){
30             psv.next = head.next;
31         }else
32         psv.next=null;
33         return dummy.next;
34     }
35 }

九章算法上的答案，还木有分析，头有点疼。。。人笨就得多训练

 1 /**
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 
 8 public class Solution {
 9     public ListNode deleteDuplicates(ListNode head) {
10         if(head == null || head.next == null)
11             return head;
12         
13         ListNode dummy = new ListNode(0);
14         dummy.next = head;
15         head = dummy;
16 
17         while (head.next != null && head.next.next != null) {
18             if (head.next.val == head.next.next.val) {
19                 int val = head.next.val;
20                 while (head.next != null && head.next.val == val) {
21                     head.next = head.next.next;
22                 }            
23             } else {
24                 head = head.next;
25             }
26         }
27         
28         return dummy.next;
29     }
30 }

8.Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

　　此题的思路与上题一致依旧是三个数三个数比较，区别就是标准放宽（只要不是(A[p]==A[q]&&A[q]==A[q+1])就可以留下A[q]），然后q自增，继续比较即可。

 1 public class Solution {
 2     public int removeDuplicates(int[] A) {
 3         if (A == null || A.length == 0||A.length == 1) {
 4             return A.length;
 5         }
 6         
 7         int p = 0;
 8         int q = p+1;
 9         
10         while(q < A.length - 1){  
11             if(!(A[p]==A[q]&&A[q]==A[q+1])){
12                 A[++p]=A[q];
13             }
14             q++;
15         }
16         A[++p]=A[q];
17         
18         return p+1;
19     }
20 }

9.Merge Two Sorted Lists

Total Accepted: 25907 Total Submissions: 77789

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

此题太简单，无需解释。

 1 /**
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 public class Solution {
 8     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 9         ListNode dummy = new ListNode(0);
10         ListNode lastNode = dummy;
11         
12         while (l1 != null && l2 != null) {
13             if (l1.val < l2.val) {
14                 lastNode.next = l1;
15                 l1 = l1.next;
16             } else {
17                 lastNode.next = l2;
18                 l2 = l2.next;
19             }
20             lastNode = lastNode.next;
21         }
22         
23         if (l1 != null) {
24             lastNode.next = l1;
25         } else {
26             lastNode.next = l2;
27         }
28         
29         return dummy.next;
30     }
31 }

我还是比较无耻的把自己的程序放上来，它节省了一个指针嘿嘿

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        dummy.next = l1;
        l1 = dummy;
        
        while(l1.next != null && l2 != null){
            if(l2.val <= l1.next.val){
                ListNode tmp = l1.next;
                l1.next = l2;
                l1 = l1.next;
                l2 = l2.next;
                l1.next = tmp;
                
            }else{
                l1 = l1.next;
            }
        }
        if(l1.next == null){
            l1.next = l2;
        }
        return dummy.next;
        
    }
}

10. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

11.Linked List Cycle II

Total Accepted: 23590 Total Submissions: 76362

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         ListNode p,q;
 4         p=q=head; 
 5         
 6         while(q!=null&&q.next!=null){
 7             p=p.next;
 8             q=q.next.next;
 9             if(p==q){break;}
10         }
11         if(q==null||q.next==null)  return null;
12         
13         p=head;
14         while(p!=q){
15             p=p.next;
16             q=q.next;
17         }
18         return q;
19     }
20 }

12.Merge Sorted Array

Total Accepted: 24531 Total Submissions: 76046

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

想写好的，结果还是没人家的好

我的：

public void merge(int A[], int m, int B[], int n) {
        if(A.length<m+n) return;
        
        for(int i = m-1;i >= 0;i--){
            A[n+i]=A[i];
        }
        int p = n;
        int q = 0;
        int k = 0;
        
        while(q<n&&p<m+n){
            if(B[q] <= A[p]){
                A[k++] = B[q];
                q++;
            }else{
                A[k++] = A[p];
                p++;
            }
        }
        if(p==m+n){
            while(k<m+n){
                A[k++]=B[q++];
            }
        }
    }

好的：

 1 /**
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 public class Solution {
 8     public void merge(int A[], int m, int B[], int n) {
 9         int index = m + n;
10         while (m > 0 && n > 0) {
11             if (A[m - 1] > B[n - 1]) {
12                 A[--index] = A[--m];
13             } else {
14                 A[--index] = B[--n];
15             }
16         }
17         while (n > 0) {
18             A[--index] = B[--n];
19         }
20     }
21 }

13.Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

　　我做这道题的思路是，首先找到那个pivot（这里pivot定义为数组中最小的，开始的那个数），这样结题就明朗了，其实就可以分两段调用折半查找就行了。分别是[pivot, len -1]和(0, (pivot-1+len)%len]。

 1 public class Solution {
 2     private int getPivot(int[] A){
 3         //pivot is the real start of the array
 4         if(A.length==1) return 0;
 5         int i = 0;
 6         while(i<A.length-1&&A[i]<A[i+1]){
 7             i++;
 8         }
 9         if(i==A.length-1)  return 0;
10         else return i+1;
11     }
12     private int binarySearch(int[] A, int k, int low, int high){
13         int mid;  
14         if(low>high)  
15             return -1;  
16         else{  
17             mid = (low+high) / 2;  
18             if(A[mid]==k)  
19                 return mid;  
20             if(k>A[mid])  
21                 return binarySearch(A,k,mid+1,high);        
22             else  
23                 return binarySearch(A,k,low,mid-1);            
24         }  
25     }
26     private int mySearch(int[] A, int target, int pivot){
27         int start = pivot;
28         int end = (pivot-1+A.length)%A.length;
29         if(target<A[start]||target>A[end]) return -1;
30         else{
31             int res1=binarySearch(A,target,start,A.length-1);
32             int res2=binarySearch(A,target,0,end);
33             if(res1==-1&&res2==-1)  return -1;
34             else return res1>res2?res1:res2;
35         }
36     }
37     public int search(int[] A, int target) {
38         if(A.length == 0) return -1;
39         return mySearch(A,target,getPivot(A));
40     }
41 }

　　来看看九章算法是怎么解的。他的解题思路很巧妙，有两点需要注意：一个是循环结束条件，另一个是如何二分。主要的核心思想其实还是折半查找，将问题保留，每次都可能将他变成正常的折半。

 1 /**
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 public class Solution {
 8     public int search(int[] A, int target) {
 9         int start = 0;
10         int end = A.length - 1;
11         int mid;
12        //每次折半，总有一半是正常的，一半是保留有rotate的
　　　　　　 //随着每次的折半都能将问题大大缩小
13         while (start + 1 < end) {    //当start跟end挨着的时候停止
14             mid = start + (end - start) / 2;
15             if (A[mid] == target) {
16                 return mid;
17             }
18             if (A[start] < A[mid]) {    //此时相对位置为start，mid，pivot（end与pivot的位置关系可变）
19                 // situation 1, red line    
20                 if (A[start] <= target && target <= A[mid]) {
21                     end = mid;   // target在start到mid之间时，该情况下为最正常的折半查找处理
22                 } else {
23                     start = mid;    //target在mid和end之间时，由下次循环判断折半后的区间再次落到那个选择
24                 }
25             } else {    //此时相对位置为start，pivot，mid，end
26                 // situation 2, green line    
27                 if (A[mid] <= target && target <= A[end]) {
28                     start = mid;    // target在mid到end之间时，该情况下为最正常的折半查找处理
29                 } else {
30                     end = mid;    // target在start到mid之间时，由下次循环判断折半后的区间再次落到那个选择
31                 }
32             }
33         } // while
34         
35         if (A[start] == target) {
36             return start;
37         }
38         if (A[end] == target) {
39             return end;
40         }
41         return -1;
42     }
43 }

14.Search in Rotated Sorted Array II

Total Accepted: 17612 Total Submissions: 57210

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

　　来，我们直接看九章

 1 /**
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 // it ends up the same as sequential search
 8 // We used linear search for this question just to indicate that the 
 9 // time complexity of this question is O(n) regardless of binary search is applied or not.
10 public class Solution {
11     public boolean search(int[] A, int target) {
12         for (int i = 0; i < A.length; i ++) {
13             if (A[i] == target) {
14                 return true;
15             }
16         }
17         return false;
18     }
19 }

　　默默觉得这道题出得有点流氓，唉，我不太会算时间复杂度，一直觉得它麻烦，改天专门研究下吧。

15.Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

 1 public class Solution {
 2     public String reverseWords(String s) {
 3         String[] str = s.trim().split(" ");
 4         StringBuilder sb = new StringBuilder();
 5         for(int i = str.length-1; i >= 0;i--){
 6             if(!str[i].isEmpty()){
 7                 sb.append(str[i]);
 8                 sb.append(" ");
 9             }
10         }
11         return sb.toString().trim();
12     }
13 }

　　很简单的一道题了，但是有点需要注意的就是，当输入为“ a b ”（三个空格，a，三个空格，b，空格）的时候，str会生成a,"", "", b这四项，其中""处理需要注意。

　　程序的第六行要使用isEmpty()方法判断，而不是if(str[i]!=null&&str[i]!="")判断，这样是没有效果的。或者使用这个也可以if (!str[i].equals(""))。

　　？？？C++是不是可以使用if(str[i]!=null&&str[i]!="")判断？不能使用它判断的原因是不是因为每个“”和“”是不同的对象，不能用==来判断？

16.Insertion Sort List

Sort a linked list using insertion sort.

本人用的思路是：

　　为了减少使用指针（比如，previous指针，用于指示当前节点的前一节点，在交换节点位置时使用），一律使用p.next来比较。

这里使用p节点作为基准点，p及p前面的节点都排好顺序，通过不断的比较找出p的后面节点在p之前的位置来排序。若p后面没有节点了，那么就可以停止了。

　　链表题最好保持一个良好的习惯，总是添加头结点。由于假设p及p以前的节点都排好序了，因此p节点应该等于第一个节点，即ListNode p = dummy.next;

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         ListNode dummy = new ListNode(-1);
 4         dummy.next = head;
 5         head = dummy;
 6         ListNode p = dummy.next;
 7         ListNode s;
 8         
 9         while(p!=null){
10             if(p.next!=null){
11                 s = p.next;
12                 p.next = p.next.next;
13                 s.next = null;
14             }else{
15                 break;
16             }
17             while(head!=p&&s.val>head.next.val){
18                 head=head.next;
19             }
20             ListNode tmp = head.next;
21             head.next = s;
22             s.next = tmp;
23             if(head==p)
24                 p=p.next;
25             
26             head=dummy;
27         }
28         return dummy.next;
29     }
30 }

其实以上程序还可以优化如下。

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         ListNode dummy = new ListNode(-1);
 4         dummy.next = head;
 5         head = dummy;
 6         ListNode p = dummy.next;
 7         ListNode s;
 8         
 9         while(p!=null){
10             if(p.next==null)  break;
11             while(head!=p&&p.next.val>head.next.val){
12                 head=head.next;
13             }
14             if(head==p)
15                 p=p.next;
16             else{
17                 s = p.next;
18                 p.next = p.next.next;
19                 s.next = null;
20                 
21                 ListNode tmp = head.next;
22                 head.next = s;
23                 s.next = tmp;
24             }
25             head=dummy;
26         }
27         return dummy.next;
28     }
29 }

我们再来看看九章算法是怎么做的（我怎么这么啰嗦）。分析：该程序的主要的算法是dummy链连接有序的节点，head作为指针对每一个节点在dummy链上选择合适的位置。该算法实现上，思路会更简洁一些。

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         ListNode dummy = new ListNode(0);
 4 
 5         while (head != null) {
 6             ListNode node = dummy;
 7             while (node.next != null && node.next.val < head.val) {
 8                 node = node.next;
 9             }
10             ListNode temp = head.next;
11             head.next = node.next;
12             node.next = head;
13             head = temp;
14         }
15 
16         return dummy.next;
17     }
18 }

17.Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 1 public class Solution {
 2     public ListNode partition(ListNode head, int x) {
 3         ListNode pre = new ListNode(-1);
 4         ListNode aft = new ListNode(-1);
 5         ListNode p = pre;
 6         ListNode a = aft;
 7         while(head!=null){
 8             if(head.val<x){
 9                 p.next = head;
10                 p = p.next;
11                 head = head.next;
12                 p.next = null;
13             }else{
14                 a.next = head;
15                 a = a.next;
16                 head = head.next;
17                 a.next = null;
18             }
19         }
20         p.next = aft.next;
21         return pre.next;
22     }
23 }

18.Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 1 public class Solution {
 2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 3         int carry = 0;
 4         ListNode rDummy = new ListNode(0);
 5         ListNode res = rDummy;
 6         int adder1,adder2,sum;
 7         while(l1!=null||l2!=null){
 8             if(l1 == null){
 9                 adder1 = 0;
10                 adder2 = l2.val;
11             }
12             else if(l2 == null){
13                 adder2 = 0;
14                 adder1 = l1.val;
15             }else{
16                 adder1 = l1.val;
17                 adder2 = l2.val;
18             }
19             
20             sum = carry+adder1+adder2;
21             if(sum < 10){
22                 carry = 0;
23             }else{
24                 sum -= 10;
25                 carry = 1;
26             }
27             res.next = new ListNode(sum);
28             res = res.next;
29             
30             if(l1 == null)
31                 l2 = l2.next;
32             else if(l2 == null)
33                 l1 = l1.next;
34             else{
35                 l1 = l1.next;
36                 l2 = l2.next;
37             }
38         }
39         if(carry != 0) 
40             res.next = new ListNode(carry);
41         return rDummy.next;
42     }
43 }

再来看看九章的，私认为它的不如我的好

 1 **
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 /**
 8  * Definition for singly-linked list.
 9  * public class ListNode {
10  *     int val;
11  *     ListNode next;
12  *     ListNode(int x) {
13  *         val = x;
14  *         next = null;
15  *     }
16  * }
17  */
18 public class Solution {
19     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
20         if(l1 == null && l2 == null) {
21             return null;
22         }
23             
24         ListNode head = new ListNode(0);
25         ListNode point = head;
26         int carry = 0;
27         while(l1 != null && l2!=null){
28             int sum = carry + l1.val + l2.val;
29             point.next = new ListNode(sum % 10);
30             carry = sum / 10;
31             l1 = l1.next;
32             l2 = l2.next;
33             point = point.next;
34         }
35         
36         while(l1 != null) {
37             int sum =  carry + l1.val;
38             point.next = new ListNode(sum % 10);
39             carry = sum /10;
40             l1 = l1.next;
41             point = point.next;
42         }
43         
44         while(l2 != null) {
45             int sum =  carry + l2.val;
46             point.next = new ListNode(sum % 10);
47             carry = sum /10;
48             l2 = l2.next;
49             point = point.next;
50         }
51         
52         if (carry != 0) {
53             point.next = new ListNode(carry);
54         }
55         return head.next;
56     }
57 }
58

19.Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 1 public class Solution {
 2     public ListNode swapPairs(ListNode head) {
 3         ListNode dummy = new ListNode(0);
 4         dummy.next = head;
 5         ListNode p = dummy;
 6         ListNode q = head;
 7         
 8         while(q!=null){
 9             if(q.next == null){
10                 p.next = q;
11                 break;
12             }
13             ListNode tmp = q.next.next;
14             p.next = q.next;
15             p = p.next;
16             p.next = q;
17             p = p.next;
18             p.next = null;
19             q = tmp;
20         }
21         return dummy.next;
22     }
23 }

九章,已经看晕了

 1 *
 2  * Copyright: NineChapter
 3  * - Algorithm Course, Mock Interview, Interview Questions
 4  * - More details on: http://www.ninechapter.com/
 5  */
 6 
 7 public class Solution {
 8     public ListNode swapPairs(ListNode head) {
 9         if(head == null || head.next == null) {
10             return head;
11         }
12         ListNode point = new ListNode(0);
13         point.next = head;
14         head = point;
15         while(point.next != null && point.next.next != null) {
16             ListNode tmp = point.next.next.next;
17             point.next.next.next = point.next;
18             point.next = point.next.next;
19             point.next.next.next = tmp;
20             point = point.next.next;
21         }
22         return head.next;
23     }
24 }
25 
26 None

20.Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

 1 public class Solution {
 2     public ListNode reverseBetween(ListNode head, int m, int n) {
 3         int i = 1;
 4         ListNode dummy = new ListNode(0);
 5         dummy.next = head;
 6         ListNode p=dummy; 
 7         
 8         ListNode[] tmpNode = new ListNode[n-m+1];
 9         
10         while(i<m){
11             p=p.next;
12             head=head.next;
13             i++;
14         }
15         while(i<=n){
16             tmpNode[i-m]=head;
17             head=head.next;
18             i++;
19         }
20         for(int k = tmpNode.length-1;k>=0;k--){
21             p.next=tmpNode[k];
22             p=p.next;
23         }
24         p.next=head;
25         return dummy.next;
26     }
27 }

没找到九章的答案，ProgramPeek还崩了，大爷的。

21.Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

刚看到此题的时候对其给的参数有点困惑，public ListNode mergeKLists(List<ListNode> lists)。由于在java中链表要么是标准的LinkedList或者ArrayList，一般性的在Leetcode中表述的形式一般是用一个单节点表述，ListNode。ListNode的next指针一直指着后面的链表，因此最开始的ListNode即代表了这个链表（其实她仅相当于链表头指针）。

 1  //一个ListNode代表一个链表
 2 public class Solution {
 3     // ①
 4     // private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>(){
 5     //     public int compare(ListNode left, ListNode right){
 6     //         //null is considered as infinite
 7     //         if(left ==  null)
 8     //             return 1;
 9     //         else if(right == null)
10     //             return -1;
11     //         else
12     //             return left.val - right.val;
13     //     }
14     // };
15     
16     //②
17     public class ListNodeComparator implements Comparator<ListNode>{
18         public int compare(ListNode left, ListNode right){
19             if(left ==  null)
20                 return 1;
21             else if(right == null)
22                 return -1;
23             else
24                 return left.val - right.val;
25         }
26     }
27     public ListNode mergeKLists(List<ListNode> lists) {
28         if(lists == null||lists.size() == 0)
29             return null;
30         Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(),new ListNodeComparator());//①ListNodeComparator
31         /*由于在使用堆排序的过程中要那个被当做最小值拿出时，那个链表就要接着出一个节点添加到堆中，
32         因此是需要保留原始链表顺序信息的，因此直接将链表加入到堆中，而不是单一的节点。
33         虽然二者在这里java的表示都是用ListNode，但是要注意区别。
34         */
35         for(ListNode node : lists){
36             if(node != null){
37                 heap.add(node);     //此时node的后续链表信息并未丢失，仍旧跟在node.next中
38             }
39         }
40         ListNode dummy = new ListNode(-1);
41         ListNode tail = dummy;
42         // dummy.next = tail;
43         while(!heap.isEmpty()){
44             ListNode head = heap.poll();
45             tail.next = head;
46             tail = head;
47             if(head.next != null){
48                 heap.add(head.next);
49             }
50         }
51         return dummy.next;
52     }
53 }

　　时间复杂度分析： Time: log(k) * n. k is number of list and n is number of total elements.

22.Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}

 1 public class Solution {
 2     private ListNode reverse(ListNode head){
 3         ListNode dummy = new ListNode(-1);
 4         while(head != null){
 5             ListNode tmp = head.next;
 6             head.next = dummy.next;
 7             dummy.next = head;
 8             head = tmp;
 9         }
10         return dummy.next;
11     }
12     private ListNode merge(ListNode front, ListNode back){
13         ListNode dummy = new ListNode(-1);
14         ListNode head = dummy;
15         for(int k = 0;front != null && back != null; k++){
16             if(k % 2 == 0){
17                 head.next = front;
18                 front = front.next;
19             }else{
20                 head.next = back;
21                 back = back.next;
22             }
23             head = head.next;
24         }
25         if(front == null)
26             head.next = back;
27         else
28             head.next = front;
29         
30         return dummy.next;
31     }
32     private ListNode getMid(ListNode head){
33         int k = 0;
34         ListNode p = head;
35         while(p != null){
36             k++;
37             p = p.next;
38         }
39         k++;
40         k /= 2;
41         while((--k) != 0){
42             head = head.next;
43         }
44         return head;
45     }
46     public void reorderList(ListNode head) {
47         if(head == null) return ;
48         ListNode mid = getMid(head);
49         ListNode tail = reverse(mid.next);
50         mid.next = null;
51         head = merge(head, tail);
52     }
53 }

九章算法中对getMid函数的改进

1     private ListNode findMiddle(ListNode head) {
2         ListNode slow = head, fast = head.next;
3         while (fast != null && fast.next != null) {
4             fast = fast.next.next;
5             slow = slow.next;
6         }
7         return slow;
8     }

23.Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

 1 public class Solution {
 2     public ListNode reverseKGroup(ListNode head, int k) {
 3         int m = k;
 4         ListNode res = null;
 5         ListNode tail = head;
 6         
 7         while(head != null){
 8             m = k;
 9             ListNode marker = head;
10             while((--m)!=0 && marker != null){
11                 marker = marker.next;
12             }//while
13             if(marker == null){
14                 if(res == null)
15                     return head;
16                 else{
17                     tail.next = head;
18                     return res;
19                 }
20             }else{
21                 m = k;
22                 ListNode nTail =tail;
23                 tail = head; 
24                 ListNode dummy = new ListNode(-1);
25                 while((m--)!=0){
26                     ListNode tmp = head.next;
27                     head.next =dummy.next;
28                     dummy.next = head;
29                     head = tmp;
30                 }//while
31                 if(tail == nTail)
32                     res = dummy.next;
33                 else
34                     nTail.next = dummy.next;
35             }//if
36             
37         }//while
38         return res;
39     }
40 }

九章的答案，今天没心情分析，改日分析之。

 1 public class Solution {
 2     public ListNode reverseKGroup(ListNode head, int k) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if(k == 0 || k == 1) return head;
 6         ListNode cur = head;
 7         int length = 0;
 8         while (cur != null){
 9             cur = cur.next;
10             length++;
11         }
12         int multi = length / k;
13         if(multi == 0) return head;
14         ListNode preTail = null, curHead = null, curTail = null;
15         ListNode preNode = null, nextNode = null;
16         cur = head;
17         for(int j = 0; j < multi; j++) {
18             preNode = null;
19             for(int i = 0; i < k; i++) {
20                 if(cur != null) {
21                     nextNode = cur.next;
22                     cur.next = preNode;
23                     preNode = cur;
24                 }
25                 if(i == 0) curTail = cur;
26                 if(i == (k - 1)) curHead = cur;
27                 cur = nextNode;
28             }
29             if(preTail == null) head = curHead;
30             else preTail.next = curHead;
31             preTail = curTail;
32         }
33         curTail.next = cur;
34         return head;
35     }
36 }

24.Maximum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

 1   public int minDepth(TreeNode root) {
 2         if(root == null)  return 0;
 3         int len = 0;
 4         Queue<TreeNode> q = new LinkedList<TreeNode>();
 5         q.offer(root);
 6         while(!q.isEmpty()){
 7             int size = q.size();
 8             len++;
 9             boolean flag = false;
10             for(int i =0; i < size; i++){
11                 TreeNode node = q.poll();
12                 if(node.left == null && node.right == null){ 
13                     flag = true;
14                     break;
15                 }else{
16                     if(node.left != null)
17                         q.add(node.left);
18                     if(node.right != null)
19                         q.add(node.right);
20                 }
21             }
22             if(flag) 
23                     break;
24         }
25         return len;
26     }

万年不变的九章：

 1 public int minDepth(TreeNode root) {
 2         if (root == null) {
 3             return 0;
 4         }
 5         return getMin(root);
 6     }
 7 
 8     public int getMin(TreeNode root){
 9         if (root == null) {
10             return Integer.MAX_VALUE;
11         }
12 
13         if (root.left == null && root.right == null) {
14             return 1;
15         }
16 
17         return Math.min(getMin(root.left), getMin(root.right)) + 1;
18     }

Path Sum

25.Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /        
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

递归

 1 public class Solution {
 2     public boolean hasPathSum(TreeNode root, int sum) {
 3         if (root == null) {
 4             return false;
 5         }
 6         if (root.left == null && root.right == null) {
 7             return sum == root.val;
 8         }
 9         return hasPathSum (root.left, sum - root.val)
10             || hasPathSum(root.right, sum - root.val);
11     }
12 }

非递归：

 1 public class Solution {
 2     public class SumNode {
 3         
 4         int cSum;
 5         SumNode parent;
 6         TreeNode t;
 7         SumNode(int c, SumNode p, TreeNode t){
 8             this.cSum = c;
 9             this.parent = p;
10             this.t = t;        
11         }
12     }
13     
14 
15     public boolean hasPathSum(TreeNode root, int sum) {
16         if(root == null) return false;
17         Queue<SumNode> q = new LinkedList<SumNode>();
18         SumNode sumNode = new SumNode(root.val,null,root);
19         q.offer(sumNode);
20 
21         while(!q.isEmpty()){
22             SumNode node = q.poll(); 
23             boolean a = (node.t.left == null && node.t.right == null);
24             if(a)
25                 if(node.cSum == sum)
26                     return true;
27             
28             if(node.t.left != null)
29                 q.offer(new SumNode(node.t.left.val + node.cSum, node, node.t.left));
30             if(node.t.right != null)
31                 q.offer(new SumNode(node.t.right.val + node.cSum, node, node.t.right));
32             
33         }
34         return false;
35     }
36 }

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /      / 
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
 3         ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
 4         ArrayList<Integer> solution = new ArrayList<Integer>();
 5 
 6         findSum(rst, solution, root, sum);
 7         return rst;
 8     }
 9 
10     private void findSum(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> solution, TreeNode root, int sum){
11         if (root == null) {
12             return;
13         }
14 
15         sum -= root.val;
16 
17         if (root.left == null && root.right == null) {
18             if (sum == 0){
19                 solution.add(root.val);
20                 result.add(new ArrayList<Integer>(solution));
21                 solution.remove(solution.size()-1);
22             }
23             return;
24         }
25 
26         solution.add(root.val);
27         findSum(result, solution, root.left, sum);
28         findSum(result, solution, root.right, sum);
29         solution.remove(solution.size()-1);
30     }
31 }