4.4 分解让复杂问题简单化

很多读者可能都知道“各个击破”的军事思想，这种思想的精髓是当敌我实力悬殊时，我们可以把强大的敌人分割开来，然后集中优势兵力打败被分割开来的小部分敌人。要一下子战胜总体很强大的敌人很困难，但战胜小股敌人就容易多了。同样，在面试中，当我们遇到复杂的大问题的时候，如果能够先把大问题分解成若干个简单的小问题，然后再逐个解决这些小问题，则可能也会容易很多。

我们可以按照解决问题的步骤来分解复杂问题，每一步解决一个小问题。比如在面试题35“复杂链表的复制”中，我们将复杂链表复制的过程分解成3个步骤。在写代码的时候我们为每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

在计算机领域有一类算法叫分治法，即“分而治之”，采用的就是各个击破的思想。我们把分解之后的小问题各个解决，然后把小问题的解决方案结合起来解决大问题。比如在面试题36“二叉搜索树与双向链表”中，转换整棵二叉树是一个大问题，我们先把这个大问题分解成转换左子树和右子树两个小问题，然后再把转换左、右子树得到的链表和根节点链接起来，就解决了整棵大问题。通常分治法都可以用递归的代码实现。

在面试题38“字符串的排列”中，我们把整个字符串分为两部分：第一个字符及它后面的所有字符。我们先拿第一个字符和后面的每个字符交换，交换之后再求后面所有字符的排列。整个字符串的排列是一个大问题，而第一个字符之后的字符串的排列是一个小问题。因此，这实际上也是分治法的应用，可以用递归实现。

面试题35：复杂链表的复制

题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个节点除了有一个m_pNext指针指向下一个节点，还有一个m_pSibling指针指向链表中的任意节点或者nullptr。节点的C++定义如下：

struct ComplexListNode

{

int m_nValue;

ComplexListNode* m_pNext;

ComplexListNode* m_pSibling;

};

图4.11是一个含有5个节点的复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向nullptr的指针没有画出。

图4.11 一个含有5个节点的复杂链表

注：在复杂链表的节点中，除了有指向下一个节点的指针（实线箭头），还有指向任意节点的指针（虚线箭头）。

听到这个问题之后，很多应聘者的第一反应是把复制过程分成两步：第一步是复制原始链表上的每个节点，并用m_pNext链接起来；第二步是设置每个节点的m_pSibling指针。假设原始链表中的某个节点N的m_pSibling指向节点S，由于S在链表中可能在N的前面也可能在N的后面，所以要定位S的位置需要从原始链表的头节点开始找。如果从原始链表的头节点开始沿着m_pNext经过s步找到节点S，那么在复制链表上节点N′的m_pSibling（记为S′）离复制链表的头节点的距离也是沿着m_pNext指针s步。用这种办法就可以为复制链表上的每个节点设置m_pSibling 指针。

对于一个含有n个节点的链表，由于定位每个节点的m_pSibling都需要从链表头节点开始经过O(n)步才能找到，因此这种方法总的时间复杂度是O(n2)。

由于上述方法的时间主要花费在定位节点的m_pSibling上面，我们试着在这方面去进行优化。我们还是分为两步：第一步仍然是复制原始链表上的每个节点N创建N′，然后把这些创建出来的节点用m_pNext链接起来。同时我们把<N,N′>的配对信息放到一个哈希表中；第二步还是设置复制链表上每个节点的m_pSibling。如果在原始链表中节点N的m_pSibling指向节点S，那么在复制链表中，对应的N′应该指向S′。由于有了哈希表，我们可以用O(1)的时间根据S找到S′。

第二种方法相当于用空间换时间。对于有n个节点的链表，我们需要一个大小为O(n)的哈希表，也就是说我们以O(n)的空间消耗把时间复杂度由O(n2)降低到O(n)。

接下来我们再换一种思路，在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个节点N创建对应的N′。这一次，我们把N′链接在N的后面。图4.11中的链表经过这一步之后的结构如图4.12所示。

图4.12 复制复杂链表的第一步

注：复制原始链表的任意节点N并创建新节点N'，再把N'链接到N的后面。

完成这一步的代码如下：

void CloneNodes(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

while(pNode != nullptr)

{

ComplexListNode* pCloned = new ComplexListNode();

pCloned->m_nValue = pNode->m_nValue;

pCloned->m_pNext = pNode->m_pNext;

pCloned->m_pSibling = nullptr;

pNode->m_pNext = pCloned;

pNode = pCloned->m_pNext;

}

}

第二步设置复制出来的节点的m_pSibling。假设原始链表上的N的m_pSibling指向节点S，那么其对应复制出来的N′是N的m_pNext指向的节点，同样S′也是S的m_pNext指向的节点。设置m_pSibling之后的链表如图4.13所示。

图4.13 复制复杂链表的第二步

注：如果原始链表上的节点N的m_pSibling指向S，则它对应的复制节点N'的m_pSibling指向S的复制节点S'。

下面是完成第二步的参考代码：

void ConnectSiblingNodes(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

while(pNode != nullptr)

{

ComplexListNode* pCloned = pNode->m_pNext;

if(pNode->m_pSibling != nullptr)

{

pCloned->m_pSibling = pNode->m_pSibling->m_pNext;

}

pNode = pCloned->m_pNext;

}

}

第三步把这个长链表拆分成两个链表：把奇数位置的节点用m_pNext链接起来就是原始链表，把偶数位置的节点用m_pNext链接起来就是复制出来的链表。图4.13中的链表拆分之后的两个链表如图4.14所示。

图4.14 复制复杂链表的第三步

注：把第二步得到的链表拆分成两个链表，奇数位置上的节点组成原始链表，偶数位置上的节点组成复制出来的链表。

要实现第三步的操作也不是很难的事情。其对应的代码如下：

ComplexListNode* ReconnectNodes(ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead;

ComplexListNode* pClonedHead = nullptr;

ComplexListNode* pClonedNode = nullptr;

if(pNode != nullptr)

{

pClonedHead = pClonedNode = pNode->m_pNext;

pNode->m_pNext = pClonedNode->m_pNext;

pNode = pNode->m_pNext;

}

while(pNode != nullptr)

{

pClonedNode->m_pNext = pNode->m_pNext;

pClonedNode = pClonedNode->m_pNext;

pNode->m_pNext = pClonedNode->m_pNext;

pNode = pNode->m_pNext;

}

return pClonedHead;

}

我们把上面三步合起来，就是复制链表的完整过程。

ComplexListNode* Clone(ComplexListNode* pHead)

{

CloneNodes(pHead);

ConnectSiblingNodes(pHead);

return ReconnectNodes(pHead);

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/35_ CopyComplexList

测试用例：

功能测试（节点中的m_pSibling指向节点自身；两个节点的m_pSibling形成环状结构；链表中只有一个节点）。

特殊输入测试（指向链表头节点的指针为nullptr指针）。

本题考点：

考查应聘者对复杂问题的思维能力。本题中的复杂链表是一种不太常见的数据结构，而且复制这种链表的过程也较为复杂。我们把复杂链表的复制过程分解成3个步骤，同时把每个步骤都用图形化的方式表示出来，这样能帮助我们厘清思路。在写代码的时候，我们为每个步骤定义一个子函数，最后在复制函数中先后调用这3个函数。有了这些清晰的思路之后再写代码，就容易多了。

考查应聘者分析时间效率和空间效率的能力。当应聘者提出第一种和第二种思路的时候，面试官会提示此时在效率上还不是最优解。这时候应聘者要能自己分析出这两种算法的时间复杂度和空间复杂度各是多少。

面试题36：二叉搜索树与双向链表

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。比如，输入图4.15中左边的二叉搜索树，则输出转换之后的排序双向链表。二叉树节点的定义如下：

struct BinaryTreeNode

{

int m_nValue;

BinaryTreeNode* m_pLeft;

BinaryTreeNode* m_pRight;

};

图4.15 一棵二叉搜索树及转换之后的排序双向链表

在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点也有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。接下来我们考虑该如何转换。

由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点，这是因为中序遍历算法的