微软等数据结构+算法面试100题全部答案集锦

作者：July、阿财。

时间：二零一一年十月十三日。

引言

无私分享造就开源的辉煌。

今是二零一一年十月十三日，明日14日即是本人刚好开博一周年。在一周年之际，特此分享出微软面试全部100题答案的完整版，以作为对本博客所有读者的回馈。

一年之前的10月14日，一个名叫July的人在一个叫csdn的论坛上开帖分享微软等公司数据结构+算法面试100题，自此，与上千网友一起做，一起思考，一起解答这些面试题目，最终成就了一个名为：结构之法算法之道的编程面试与算法研究并重的博客，如今，此博客影响力逐步渗透到海外，及至到整个互联网。

在此之前，由于本人笨拙，这微软面试100题的答案只整理到了前60题（第1-60题答案可到本人资源下载处下载：www.wendangwang.com），故此，常有朋友留言或来信询问后面40题的答案。只是因个人认为：一、答案只是作为一个参考，不可太过依赖；二、常常因一些事情耽搁（如在整理最新的今年九月、十月份的面试题：、最新面试十一题）；三、个人正在针对那100题一题一题的写文章，多种思路，不断优化，即成程序员编程。自此，后面40题的答案迟迟未得整理。且个人已经整理的前60题的答案，在我看来，是有诸多问题与弊端的，甚至很多答案都是错误的。

互联网总是能给人带来惊喜。前几日，一位现居美国加州的名叫阿财的朋友发来一封邮件，并把他自己做的全部100题的答案一并发予给我，自此，便似遇见了知己。十分感谢。

任何东西只有分享出来才更显其价值。本只需贴出后面40题的答案，因为前60题的答案本人早已整理上传至网上，但多一种思路多一种参考亦未尝不可。特此，把阿财的答案再稍加整理番，然后把全部100题的答案现今都贴出来。若有任何问题，欢迎不吝指正。谢谢。

上千上万的人都关注过此100题，且大都都各自贡献了自己的思路，或回复于微软100题维护地址上，或回复于本博客内，人数众多，无法一一标明，特此向他们诸位表示敬意和感谢。谢谢大家，诸君的努力足以影响整个互联网，咱们已经迎来一个分享互利的新时代。

微软面试100题全部答案最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过。且因尊重阿财，未作过多修改。因此，有些答案是有问题的，重点还可关注本人的，亦可参考个人之前整理的前60题的答案：第1题-20题答案：www.wendangwang.com，第21-40题答案：www.wendangwang.com，第41-60题答案：）：

1.把二元查找树转变成排序的双向链表

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/\

614

/\/\

481216

转换成双向链表

4=6=8=10=12=14=16。