微软的22道数据结构算法面试题
1、反转一个链表。循环算法。
1 List reverse(List l) {
2 if(!l) return l;
3 list cur = l.next;
4 list pre = l;
5 list tmp;
6 pre.next = null;
7 while ( cur ) {
8 tmp = cur;
9 cur = cur.next;
10 tmp.next = pre
11 pre = tmp;
12 }
13 return tmp;
14 }
2、反转一个链表。递归算法。
1 List resverse(list l) {
2 if(!l || !l.next) return l;
3
4 List n = reverse(l.next);
5 l.next.next = l;
6 l.next=null;
7 }
8 return n;
9 }
3、广度优先遍历二叉树。
1 void BST(Tree t) {
2 Queue q = new Queue();
3 q.enque(t);
4 Tree t = q.deque();
5 while(t) {
6 System.out.println(t.value);
7 q.enque(t.left);
8 q.enque(t.right);
9 t = q.deque();
10 }
11 }
----------------------
1class Node {
2 Tree t;
3 Node next;
4 }
5class Queue {
6 Node head;
7 Node tail;
8 public void enque(Tree t){
9 Node n = new Node();
10 n.t = t;
11 if(!tail){
12 tail = head = n;
13 } else {
14 tail.next = n;
15 tail = n;
16 }
17 }
18 public Tree deque() {
19 if (!head) {
20 return null;
21 } else {
22 Node n = head;
23 head = head.next;
24 return n.t;
25 }
26}
4、输出一个字符串所有排列。注意有重复字符。
1char[] p;
2void perm(char s[], int i, int n){
3 int j;
4 char temp;
5 for(j=0;j<n;++j){
6 if(j!=0 && s[j]==s[j-1]);
7 elseif(s[j]!='@'){
8 p[i]=s[j];
9 s[j]='@';
10 if(i==n-1){
11 p[n]='\0';
12 printf("%s", p);
13 }else{
14 perm(s,i+1,n);
15 }
16 s[j]=p[i];
17 }
18 }
19}
--------------------------
1void main() {
2 char s[N];
3 sort(s);
4 perm(s,0,strlen(s));
5}