互联网IT公司面试指导手册

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 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(\

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}

5、输入一个字符串，输出长型整数。 1 long atol(char *str){ 2 char *p = str; 3 long l=1;m=0; 4 if (*p=='-') { 5 l=-1; 6 ++p; 7 }

8 while(isDigit(*p)){ 9 m = m*10 + p; 10 ++p;

11 }

12 if(!p) return m*l; 13 else return error; 14}

6、判断一个链表是否有循环。 1 int isLoop(List l) { 2 if ( ! l) return - 1 ; 3 List s = l.next; 4 while (s && s != l) { 5 s = s.next; 6 }

7 if ( ! s) return - 1 ; 8 else reutrn 1 ; 9 } -----------

1int isLoop(List l){ 2 if(!l) return 0; 3 p=l.next;

4 wihle(p!=l&&p!=null) { 5 l.next=l; 6 l=p;p=p.next; 7 }

8 if(p=l) return 1; 9 return 0;