Question

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表结点定义如下：

解决与链表相关的问题总是有大量的指针操作，而指针操作的代码总是容易出错的。很多面试官喜欢出链表相关的问题，就是想通过指针操作来考查应聘者的编码功底。为了避免出错，我们最好先进行全面的分析。在实际软件开发周期中，设计的时间通常不会比编码的时间短。在面试的时候我们不要急于动手写代码，而是一开始仔细分析和设计，这将会给面试官留下很好的印象。与其很快写出一段漏洞百出的代码，倒不如仔细分析再写出鲁棒的代码。

为了正确地反转一个链表，需要调整链表中指针的方向。为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观地分析。在图3.6（a）所示的链表中，h、i和j是3个相邻的结点。假设经过若干操作，我们已经把结点h之前的指针调整完毕，这些结点的m_pNext都指向前面一个结点。接下来我们把i的m_pNext指向h，此时的链表结构如图3.6（b）所示。

图3.6　反转链表中结点的m_pNext指针导致链表出现断裂

注：（a）一个链表。（b）把i之前所有的结点的m_pNext都指向前一个结点，导致链表在结点i、j之间断裂。

不难注意到，由于结点i的m_pNext指向了它的前一个结点，导致我们无法在链表中遍历到结点j。为了避免链表在结点i处断开，我们需要在调整结点i的m_pNext之前，把结点j保存下来。

也就是说我们在调整结点i的m_pNext指针时，除了需要知道结点i本身之外，还需要i的前一个结点h，因为我们需要把结点i的m_pNext指向结点h。同时，我们还事先需要保存i的一个结点j，以防止链表断开。因此相应地我们需要定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。

最后我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾结点。什么结点是尾结点？自然是m_pNext为NULL的结点。

有了前面的分析，我们不难写出如下代码：

在面试的过程中，我们发现应聘者的代码中经常出现如下3种问题：

- 输入的链表头指针为NULL或者整个链表只有一个结点时，程序立即崩溃。

- 反转后的链表出现断裂。

- 返回的反转之后的头结点不是原始链表的尾结点。

在实际面试的时候，不同应聘者的思路各不相同，因此写出的代码也不一样。那么应聘者如何才能及时发现并纠正代码中的问题，以确保不犯上述错误呢？一个很好的办法就是提前想好测试用例。在写出代码之后，立即用事先准备好的测试用例检查测试。如果面试是以手写代码的方式，那也要在心里默默运行代码做单元测试。只有确保代码通过测试之后，再提交面试官。我们要记住一点：自己多花时间找出问题并修正问题，比在面试官找出问题之后再去慌慌张张修改代码要好得多。其实面试官检查应聘者代码的方法也是用他事先准备好的测试用例来测试。如果应聘者能够想到这些测试用例，并用它们来检查测试自己的代码，那就能保证有备无患、万无一失了。

以这道题为例，我们至少应该想到几类测试用例对代码做功能测试：

- 输入的链表头指针是NULL。

- 输入的链表只有一个结点。

- 输入的链表有多个结点。

如果我们确信代码能够通过这3类测试用例的测试，那我们就有很大的把握能够通过这轮面试了。

源代码：

本题完整的源代码详见16_ReverseList项目。

测试用例：

- 功能测试（输入的链表含有多个结点，链表中只有一个结点）。

- 特殊输入测试（链表头结点为NULL指针）。

本题考点：

- 考查应聘者对链表、指针的编程能力。

- 特别注重考查应聘者思维的全面性及写出来的代码的鲁棒性。

本题扩展：

用递归实现同样的反转链表的功能。