微软的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}