Q: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.fine the parent of the node after which the list needed to be reversed, if necessary
2.reverse the nodes needed to be reversed
3.reconnect the fist half of the original list with the new head of the reversed list, if necessary;
reconnect the end of the reversed list with the rest of the list. # Reorder List

Q：Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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. find the end of the new list;
2. push the rest of the nodes into stack;
3. pop and merge nodes into the list;
(When dealing with linkedlist, always remember to break the link when necessary!!) 1. find the end of the new list and break the original list into two halves according to that node;
2. reverse the second list;
3. merge two lists; Pictures from here. A great place!

# Pascal’s Triangle

Q:Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
,
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Q2:Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

# Flatten Binary Tree to Linked List

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

For example,
Given

1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

# Binary Tree Level Order Traversal

Q:Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7```

return its level order traversal as:

```[
,
[9,20],
[15,7]
]``` V2: Bottom-up.
Q:Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
,
]

The only thing changed is line 33. # combination

Q：Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

# Permutation

Q:

Given a collection of numbers, return all possible permutations.

For example,
`[1,2,3]` have the following permutations:
`[1,2,3]``[1,3,2]``[2,1,3]``[2,3,1]``[3,1,2]`, and `[3,2,1]`. Version 2: with duplicates.

Q:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
`[1,1,2]` have the following unique permutations:
`[1,1,2]``[1,2,1]`, and `[2,1,1]`. V1-Just print it out:

```public void main(String[] arg){
char[] a ={'a','b','c'};
perm(a,0,a.length-1);
}

public void perm(char[] a, int k, int n){
if(k==n){//print
System.out.println("");
for(int i = 0; i<a.length;i++)	System.out.print(a[i]);
}else{
for(int i = k; i<=n;i++){
//swap a[k] and a[i]
char p = a[k];a[k]=a[i];a[i]=p;
perm(a,k+1,n);
//swap back a[k] and a[i]
char g = a[k];a[k]=a[i];a[i]=g;
}
}
}
```

# Return the String of a number’s binary representation

Q:Given a number, return the String of it’s binary representation

This function only work for positive integer!

```String decToBin(int n){
if(n==0) return new String("0");
StringBuilder r=new StringBuilder();
while(n!=0){
//get bit
if((n&(1<<0))==0) r.insert(0, "0");
else r.insert(0,"1");
n=n>>>1;
}
return r.toString();
//or you could use r.append() in above
//and use r.reverse().toString(); in here
}
```

# Factorial Zeros

Q: Without using a calculator, how many zeros are at the end of n! ?

Each zero comes from 2*5. Since 2 appear more frequent than 5, the number of 5s is also the number of 10s in the factorization. (for number that’s greater than 5^2, i.e, 25, 75, they have at least 2 5s. For number that’s greater than 5^3, they have at least 3 5s. And so on.)

```int getZ(int n){
//This function return the number of zeros at the end of n!
int z=0;
if(n<5) return 0;
for(int i=5;i<=n;i++){
int c=1;
while(i%(Math.pow(5, c))==0){
c++;
}
z+=c-1;
}
return z;
}
```

# Quick Select (fine the kth element of an unsorted array)

Q:fine the kth element of an unsorted array
Time complexity: O(n).

```//if k=0, then is the smallest element
//if k=1, then is the second smallest element, and so on
int selectKth(int[] arr, int k) {
if (arr == null || arr.length <= k)
throw new Error();

int from = 0, to = arr.length - 1;

// if from == to we reached the kth element
while (from < to) {
int r = from, w = to;
int mid = arr[(r + w) / 2];

// stop if the reader and writer meets
while (r < w) {

if (arr[r] >= mid) { // put the large values at the end
int tmp = arr[w];
arr[w] = arr[r];
arr[r] = tmp;
w--;
} else { // the value is smaller than the pivot, skip
r++;
}
}
// if we stepped up (r++) we need to step one down
if (arr[r] > mid)
r--;
// the r pointer is on the end of the first k elements
if (k <= r) {
to = r;
} else {
from = r + 1;
}
}

return arr[k];
}
```

From here.