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函数。

　　编辑特别推荐:

　　Microsoft面试题

　　微软认证考试:70064Windows95考生回顾（1）