12.2在找工作面试的时候，面试官常常会要求应聘者现场在纸上写一些算法程序。这样可以考察应聘者对数据结构和基本算法的熟练程度。本节我们就选取一些面试程序题中的典型代表加以讲解，让读者能够对这类算法题有一个初步的了解。 12.2.1遍历一次求取单链表的中间点【问题描述】如何在遍历一次的条件下，求出链表的中间结点。 【分析】单链表是简单、基础的一类数据结构，由于它简单的结构，相对容易的实现代码，以及灵活的应用模式，成了面试考题的宠儿。链表是一种相对动态的数据结构，可随时向链表中添加结点（只要有足够的内存），添加结点时，需要为新结点分配内存，然后调整指针的指向来确保新结点被连接到链表中。由于链表中的内存不是一次性分配的，我们无法保证链表和数组一样是连续的。因此如果想在链表中找到它的第i个结点，就必须从头结点开始，沿着指向下一个结点的指针遍历链表。本题要求我们在不知道链表长度的情况下，找出链表的中间结点。其实，单链表是线性数据结构，我们可以把它当成一条直线，想象一下我们中学时所做过的一些物理题，经常会让我们去计算一条路的中点，那我们用的是什么方法呢？一般我们会设定两辆汽车，一辆快车，一辆慢车，其中快车的速度是慢车的两倍，这样两辆车同时从起点出发，当快车到达终点时，慢车正好到达这条路的中心点。同样的，我们在这道题中，引入两个指针，一个快指针，一个慢指针，快指针的移动速度是慢指针的两倍，快指针每次移动两个结点，慢指针每次移动一个结点，这样，当快指针到达单链表末尾的时候，慢指针刚好到达链表的中间结点。按照这个思路，我们的实现代码如下：图12-2运行结果