Build BST from sorted array and Linked List

Q:Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

My Answer:
sa

Q: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.

My Answer:
lis

It’s more efficient to build a sorted array fist and use that array to build the BST. This require O(n) space and O(n) time.
 

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
}

List Flattening and List Unflattening

Q:PIE P:53

These function haven’t been tested yet.
List Flattening:

void flattenList(Node head,Node tail){
if(head==null) return; //empty linkedlist
Node curr = head;
Node childTail;       
//childTail is used for finding the tail of the child
		
/**Traverse through the list **/
while(curr.next!=null){			
/**Find child**/
if(curr.child!=null){
/**After found a child, 
//1)link the child to the tail 
//2)find the tail of the child's list 
//3)update tail**/
				
/**1)link the child to the tail**/
tail.next=curr.child;
curr.child.prev=tail;
				
/**2)find the tail of the child's list**/
childTail=curr.child;
while(childTail.next!=null){
childTail=childTail.next;
}
				
/**3)update tail**/
tail=childTail;
}
curr=curr.next;
}
}

List Unflatterning:

void unflattenList(Node head, Node tail){		
if(head==null) return;
Node curr=head;
		
/**Traverse through the list 1st time & breaking the prev link of child; 
//the breaking prev link is a mark of a child**/
while(curr.next!=null){
/**Find a child**/
if(curr.child!=null){
/**Break the prev link**/
curr.child.prev=null;
}
curr=curr.next;
}
		
/**Traverse through the list 1st time & breaking the next link which links to a child**/
Node prevNode=head;
curr=head.next;
while(curr.next!=null){
/**Find a child**/
if(curr.prev==null){
/**Breaking the next link**/
prevNode.next=null;				
}
prevNode=curr;
curr=curr.next;
}
		
/**Update the tail**/
curr=head;
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}

List Unflattening, using recursion.
/*
* Algorithm:
* Explore path:
* While not at the end
* If current node has a child
* Separate the child from its previous node
* Explore path beginning with the child
* Go onto the next node
*/

 
void unflattenList(Node head,Node tail){
/**Find child and break links**/
findAndBreak(head);
		
/**Update the tail**/
Node curr=head;
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}
	
void findAndBreak(Node head){
Node curr=head.next;
		
while(curr.next!=null){
next=curr.next;            
/**Find a child**/
if(curr.child!=null){
Node child = curr.child;
/**Break links**/
child.prev.next=null;
child.prev=null;
/** findAndBreak the child list**/
findAndBreak(child);
}
/**Go on to the next node**/
curr=next;
}
}