8} 9
16、返回一颗二叉树的深度。 1int depth(Tree t){ 2 if(!t) return 0; 3 else {
4 int a=depth(t.right); 5 int b=depth(t.left); 6 return (a>b)?(a+1):(b+1); 7 } 8}
17、两个链表，一升一降。合并为一个升序链表。 1 List merge(List a, List d) { 2 List a1 = reverse(d); 3 List p = q = new List(); 4 while ( a && a1 ) { 5 if (a.value < a1.value) { 6 p.next = a; 7 a = a.next; 8 } else { 9 p.next = a1; 10 a1 = a1.next; 11 }
12 p = p.next;
13 }
14 if (a) p.next = a; 15 elseif(a1) p.next = a1; 16 return q.next; 17 }
18、将长型转换为字符串。 1char* ltoa(long l){ 2 char[N] str; 3 int i=1,n=1;
4 while(!(l/i<10)){i*=10;++n}
5 char* str=(char*)malloc(n*sizeof(char)); 6 int j=0; 7 while(l){ 8 str[j++]=l/i; 9 l=l%i; 10 i/=10; 11 }
12 return str; 13}
19、用一个数据结构实现 1 if (x == 0) y = a; 2 else y = b; 1 j[] = {a,b}; 2 y=j[x];
20、在双向链表中删除指定元素。 1void del(List head, List node){ 2 List pre=new List(); 3 pre.next = head; 4 List cur = head; 5 while(cur && cur!=node){ 6 cur=cur.next; 7 pre=pre.next; 8 }
9 if(!cur) return; 10 List post = cur.next; 11 pre.next=cur.next; 12 post.last=cur.last; 13 return; 14}
21、不重复地输出升序数组中的元素。 1 void outputUnique( char [] str, int n) { 2 if (n <= 0 ) return ;
3 elseif(n == 1 ) putchar(str[ 0 ]); 4 else {
5 int i = 0 ,j = 1 ; 6 putchar(str[ 0 ]); 7 while (j < n) {
8 if (str[j] !== str[i]) {
9 putchar(str[j]); 10 i = j; 11 } 12 ++ j; 13 } 14 } 15 }
22、面试过程中我还遇到了下面几题：
1、如何删除链表的倒数第m的元素?我的方法是先用pre指针从链表头开始步进m，新建pst节点next指针指向头节点，cur指针指向头节点，然后pre，cur，post三个指针一起步进，当pre指向链表结尾的时候cur指向倒数第m个元素，最后利用pst指针删除cur指向元素。 2、如何判断一个字符串是对称的?如a，aa，aba。设置头尾指针同时向中间比较靠齐直至相遇。
3、如何利用2函数找出一个字符串中的所有对称子串?以子串头指针和尾指针为循环变量设置两个嵌套的循环以找出所有子串，对每个子串应用2函数。
互联网IT公司面试指导手册
