微軟算法面試題

1、反轉(zhuǎn)一個(gè)鏈表。循環(huán)算法。

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、反轉(zhuǎn)一個(gè)鏈表。遞歸算法。

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、廣度優(yōu)先遍歷二叉樹(shù)。

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、輸出一個(gè)字符串所有排列。注意有重復(fù)字符。

1char[] p;

2void perm(char s[], int i, int n){

3 int j;

4 char temp;

5 for(j=0;j<n;++j){< p="">

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]='