# Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

```public TreeNode sortedListToBST(ListNode head) {
return null;
}
TreeNode root = new TreeNode(mid.val);
ListNode midPost = mid.next;
}
root.right = sortedListToBST(midPost);

return root;

}

}
ListNode pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
//Remember to set pre.next = null
if (pre != null) {
pre.next = null;
}
return slow;
}```

# Remove Nth Node From End of List

#### Remove Nth Node From End of List

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

Example

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

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

The minimum number of nodes in list is n.

Challenge

O(n) time

Solution: One Pass using Fast Slow Pointers

O(n) time, O(1) space

```ListNode removeNthFromEnd(ListNode head, int n) {
return null;
}
ListNode fast = slow;
for (int i = 0; i < n; i++) {
if (fast.next == null) {
}
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
}```

http://www.cnblogs.com/hiddenfox/p/3408931.html

http://www.cnblogs.com/wuyuegb2312/p/3183214.html

# Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

One pass version:

```public class Solution {
public void sortColors(int[] A) {
int red = 0;
int blue = A.length-1;
int runner = 0;
while(runner<=blue){
switch(A[runner]){
case 0:
swap(A, red, runner);
red++;
runner++;
break;
case 1:
runner++;
break;
case 2:
swap(A, blue, runner);
blue--;
break;
}
}
}

public void swap(int[] A, int a, int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
}```