3.4 代码的鲁棒性

鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。

容错性是鲁棒性的一个重要体现。不鲁棒的软件在发生异常事件的时候，比如用户输入错误的用户名、试图打开的文件不存在或者网络不能连接，就会出现不可预见的诡异行为，或者干脆整个软件崩溃。这样的软件对于用户而言，不亚于一场灾难。

由于鲁棒性对软件开发非常重要，所以面试官在招聘的时候对应聘者写出的代码是否鲁棒也非常关注。提高代码的鲁棒性的有效途径是进行防御性编程。防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。比如，当试图打开文件时发现文件不存在，可以提示用户检查文件名和路径；当服务器连接不上时，可以试图连接备用服务器等。这样，当异常情况发生时，软件的行为也尽在我们的掌握之中，而不至于出现不可预见的事情。

在面试时，最简单也最实用的防御性编程就是在函数入口添加代码以验证用户输入是否符合要求。通常面试要求的是写一两个函数，我们需要格外关注这些函数的输入参数。如果输入的是一个指针，那么指针是空指针怎么办？如果输入的是一个字符串，那么字符串的内容为空怎么办？如果能把这些问题都提前考虑到，并进行相应的处理，那么面试官就会觉得我们有防御性编程的习惯，能够写出鲁棒的软件。

当然，并不是所有与鲁棒性相关的问题都只是检查输入的参数这么简单。我们看到问题的时候，要多问几个“如果不……那么……”这样的问题。比如面试题22“链表中倒数第k个节点”，这里就隐含着一个条件，即链表中节点的个数大于k。我们就要问：如果链表中节点的数目不是大于k个，那么代码会出现什么问题？这样的思考方式能够帮助我们发现潜在的问题并提前解决问题。这比让面试官发现问题之后我们再去慌忙分析代码、查找问题的根源要好得多。

面试题22：链表中倒数第k个节点

题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。链表节点定义如下：

struct ListNode

{

int m_nValue;

ListNode* m_pNext;

};

为了得到倒数第k个节点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表节点的定义可以看出，本题中的链表是单向链表，单向链表的节点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。

既然不能从尾节点开始遍历这个链表，我们还是把思路回到头节点上来。假设整个链表有n个节点，那么倒数第k个节点就是从头节点开始的第n-k+1个节点。如果我们能够得到链表中节点的个数n，那么只要从头节点开始往后走n-k+1步就可以了。如何得到节点数n？这个不难，只需要从头开始遍历链表，每经过一个节点，计数器加1就行了。

也就是说我们需要遍历链表两次，第一次统计出链表中节点的个数，第二次就能找到倒数第k个节点。但是当我们把这种思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次。

为了实现只遍历链表一次就能找到倒数第k个节点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾节点时，第二个（走在后面的）指针正好指向倒数第k个节点。

下面以在有6个节点的链表中找倒数第3个节点为例分析这种思路的过程。首先用第一个指针从头节点开始向前走两（2=3-1）步到达第3个节点，如图3.7（a）所示。接着把第二个指针初始化指向链表的第一个节点，如图3.7（b）所示。最后让两个指针同时向前遍历，当第一个指针到达链表的尾节点时，第二个指针指向的刚好就是倒数第3个节点，如图3.7（c）所示。

想清楚这种思路之后，很多人很快就能写出如下代码：

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)

{

ListNode *pAhead = pListHead;

ListNode *pBehind = nullptr;

for(unsigned int i = 0; i < k - 1; ++ i)

{

pAhead = pAhead->m_pNext;

}

pBehind = pListHead;

while(pAhead->m_pNext != nullptr)

{

pAhead = pAhead->m_pNext;

pBehind = pBehind->m_pNext;

}

return pBehind;

}

图3.7 在有6个节点的链表上找倒数第3个节点的过程

注：（a）第一个指针在链表上走两步。（b）把第二个指针指向链表的头节点。（c）两个指针一同沿着链表向前走。当第一个指针指向链表的尾节点时，第二个指针指向倒数第3个节点。

有不少人在面试之前从网上看到过用两个指针遍历的思路来解这道题，因此听到面试官问这道题，他们心中一阵窃喜，很快就能写出代码。可是几天之后他们等来的不是Offer，而是拒信，于是百思不得其解。其实原因很简单，就是自己写的代码不够鲁棒。以上面的代码为例，面试官可以找出3种办法让这段代码崩溃。

（1）输入的pListHead为空指针。由于代码会试图访问空指针指向的内存，从而造成程序崩溃。

（2）输入的以pListHead为头节点的链表的节点总数少于k。由于在for循环中会在链表上向前走k-1步，仍然会由于空指针而造成程序崩溃。

（3）输入的参数k为0。由于k是一个无符号整数，那么在for循环中k-1得到的将不是-1，而是4294967295（无符号的0xFFFFFFFF）。因此，for循环执行的次数远远超出我们的预计，同样也会造成程序崩溃。

这么简单的代码却存在3个潜在崩溃的风险，我们可以想象当面试官看到这样的代码时会有什么样的心情，最终他给出的是拒信而不是Offer虽是意料之外，但也在情理之中。

面试小提示：

面试过程中写代码要特别注意鲁棒性。如果写出的代码存在多处崩溃的风险，那么我们很有可能和Offer失之交臂。

针对前面指出的3个问题，我们要分别处理。如果输入的链表头指针为nullptr，那么整个链表为空，此时查找倒数第k个节点自然应该返回nullptr。如果输入的k是0，也就是试图查找倒数第0个节点，由于我们计数是从1开始的，因此输入0没有实际意义，也可以返回nullptr。如果链表的节点数少于k，那么在for循环中遍历链表可能会出现指向nullptr的m_pNext，因此我们在for循环中应该加一个if判断。修改之后的代码如下：

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)

{

if(pListHead == nullptr || k == 0)

return nullptr;

ListNode *pAhead = pListHead;

ListNode *pBehind = nullptr;

for(unsigned int i = 0; i < k - 1; ++ i)

{

if(pAhead->m_pNext != nullptr)

pAhead = pAhead->m_pNext;

else

{

return nullptr;

}

}

pBehind = pListHead;

while(pAhead->m_pNext != nullptr)

{

pAhead = pAhead->m_pNext;

pBehind = pBehind->m_pNext;

}

return pBehind;

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/22_ KthNodeFromEnd

测试用例：

功能测试（第k个节点在链表的中间；第k个节点是链表的头节点；第k个节点是链表的尾节点）。

特殊输入测试（链表头节点为nullptr指针；链表的节点总数少于k；k等于0）。

本题考点：

考查应聘者对链表的理解。

考查应聘者所写代码的鲁棒性。鲁棒性是解决这道题的关键所在。如果应聘者写出的代码有着多处崩溃的潜在风险，那么他是很难通过这轮面试的。

相关题目：

求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果节点总数是偶数，则返回中间两个节点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

举一反三：

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

面试题23：链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点？例如，在如图3.8所示的链表中，环的入口节点是节点3。

解决这个问题的第一步是如何确定一个链表中包含环。受到面试题22的启发，我们可以用两个指针来解决这个问题。和前面的问题一样，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；如果走得快的指针走到了链表的末尾（m_pNext指向NULL）都没有追上第一个指针，那么链表就不包含环。

第二步是如何找到环的入口。我们还是可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。

图3.8 节点3是链表中环的入口节点

以图3.8为例分析两个指针的移动规律。指针P1和P2在初始化时都指向链表的头节点，如图3.9（a）所示。由于环中有4个节点，所以指针P1先在链表上向前移动4步，如图3.9（b）所示。接下来两个指针以相同的速度在链表上向前移动，直到它们相遇。它们相遇的节点正好是环的入口节点，如图3.9（c）所示。

剩下的问题是如何得到环中节点的数目。我们在前面提到判断一个链表里是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。

图3.9 在有环的链表中找到环的入口节点的步骤

注：（1）指针P1和P2在初始化时都指向链表的头节点。（2）由于环中有4个节点，所以指针P1先在链表上向前移动4步。（3）指针P1和P2以相同的速度在链表上向前移动，直到它们相遇。它们相遇的节点就是环的入口节点。

下面代码中的函数MeetingNode在链表中存在环的前提下找到一快一慢两个指针相遇的节点。

ListNode* MeetingNode(ListNode* pHead)

{

if(pHead == nullptr)

return nullptr;

ListNode* pSlow = pHead->m_pNext;

if(pSlow == nullptr)

return nullptr;

ListNode* pFast = pSlow->m_pNext;

while(pFast != nullptr && pSlow != nullptr)

{

if(pFast == pSlow)

return pFast;

pSlow = pSlow->m_pNext;

pFast = pFast->m_pNext;

if(pFast != nullptr)

pFast = pFast->m_pNext;

}

return nullptr;

}

如果链表中不存在环，那么函数MeetingNode返回nullptr。

在找到环中任意一个节点之后，就能得出环中的节点数目，并找到环的入口节点。相应的代码如下：

ListNode* EntryNodeOfLoop(ListNode* pHead)

{

ListNode* meetingNode = MeetingNode(pHead);

if(meetingNode == nullptr)

return nullptr;

// 得到环中节点的数目

int nodesInLoop = 1;

ListNode* pNode1 = meetingNode;