Reverse Linked List

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.

My Answer:
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.

asc

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}.

My Answer: using stack
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!!)

rl

Better Answer!
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;

oo

Remark:
Reverse a list:
reverse-list

Merge two lists:
merge-list-in-place

Pictures from here. A great place!

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:

[
  [3],
  [9,20],
  [15,7]
]

My Answer:

BTL

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],
[3],
]

My Answer:
The only thing changed is line 33.
btbu

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].

My Answer:

permi

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].

permi2

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

My Answer:
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! ?

Answer:
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).
Answer:

//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.