分治法:把分解后的小问题各个解决,然后把小问题的解决方案结合起来解决大问题。
面试题35:复杂链表的复制。请实现函数ComplexListNode* Clone(ComplexListNode* pHead)
,复制一个复杂链表。在复杂链表中,每个节点除了有一个m_pNext指针指向下一个节点,还有一个m_pSibling指针指向链表中任意节点或者nullptr。节点定义如下:
struct ComplexListNode {
int m_nValue;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
};
这个问题很多人的方法是把复制过程分为两步,第一步复制原始链表上的每个节点,再用m_pNext链接起来;第二步是设置每个节点的m_pSibling指针。对于第二步,找到一个节点的m_pSibling指针指向的节点需要从头结点沿着m_pNext遍历链表,因为我们不知道m_pSibling指向的节点在当前节点的前面还是后面。对于一个含有n个结点的复杂链表,这种方法的总的时间复杂度是O(n²)。
以上方法的时间主要花费在定位节点的m_pSibling指针指向的节点上,我们可以优化第二步:将原始链表的节点N和新链表的节点n放到一个哈希表中,用<N,n>表示,若原始链表中节点N的m_pSibling指向节点S,那么新链表中节点n的m_pSibling指向s,有了哈希表,我们可以用O(1)的时间根据S找到s。这种方法相当于以空间换时间,对于n个节点的复杂链表,我们需要一个大小为O(n)的哈希表,把时间复杂度降为了O(n)。
还有一种思路,可以不用辅助空间就实现O(n)的时间效率。第一步,将根据原始节点创建的新节点插入到原始节点后边;第二步设置新创建节点的m_pSibling指针,如原始链表上节点N的m_pSibling指向S,则它的对应复制节点n的m_pSibling指向s;第三步把长链表拆分为两个链表:
#include <iostream>
#include <stack>
using namespace std;
struct ComplexListNode {
int m_nValue;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
};
void printListReversingly_iteratively(ComplexListNode* pHead) {
stack<ComplexListNode*> nodes;
ComplexListNode* pNode = pHead;
while (pNode != nullptr) { // 将链表从头到尾压栈
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while (!nodes.empty()) { // 打印栈中内容
cout << nodes.top()->m_nValue << endl; // 打印栈顶值
nodes.pop(); // 栈顶元素出栈
}
}
void CloneNodes(ComplexListNode* pHead) { // 第一步,克隆节点
while (pHead) {
ComplexListNode* pNode = new ComplexListNode();
pNode->m_nValue = pHead->m_nValue;
pNode->m_pSibling = pHead->m_pSibling; // 给pNode赋值
pNode->m_pNext = pHead->m_pNext;
pHead->m_pNext = pNode; // 将pNode插入到链表
pHead = pNode->m_pNext; // 继续复制下一个节点
}
}
void ConnectSiblingNode(ComplexListNode* pHead) { // 第二步,设置新节点的m_pSibling指针
while (pHead) {
if (pHead->m_pSibling != nullptr) { // 当pHead的m_pSibling指针不为空时
pHead->m_pNext->m_pSibling = pHead->m_pSibling->m_pNext;
}
pHead = pHead->m_pNext->m_pNext;
}
}
ComplexListNode* ReconnectNodes(ComplexListNode* pHead) { // 第三步,分链表
ComplexListNode* newList = pHead->m_pNext, *oldList = pHead; // 分成的两个链表的头节点
ComplexListNode* pNewNode, *pOldNode = pHead; // 分别指向新旧两个链表中的节点
while (pOldNode->m_pNext->m_pNext) { // 当原链表节点没结束时
pNewNode = pOldNode->m_pNext; // 更新新节点为下一个新节点
pOldNode->m_pNext = pNewNode->m_pNext; // 将指向新节点的指针指向新节点的后一个节点
pNewNode->m_pNext = pNewNode->m_pNext->m_pNext; // 将新节点的后继指针指向下一个新节点
pOldNode = pOldNode->m_pNext;
}
pOldNode->m_pNext = nullptr; // 因为循环只能到最后两个新旧节点还没分开的状态,需要将最后一个旧节点与最后一个新节点分开
cout << "反向打印旧链表验证旧链表状态:" << endl;
printListReversingly_iteratively(oldList);
return newList;
}
ComplexListNode* Clone(ComplexListNode* pHead) {
if (pHead == nullptr) {
return nullptr;
}
CloneNodes(pHead); // 第一步,克隆节点
ConnectSiblingNode(pHead); // 第二步,设置新节点的m_pSibling指针
return ReconnectNodes(pHead); // 第三步,分链表
}
int main() {
ComplexListNode* pNode1 = new ComplexListNode();
ComplexListNode* pNode2 = new ComplexListNode();
ComplexListNode* pNode3 = new ComplexListNode();
ComplexListNode* pNode4 = new ComplexListNode();
ComplexListNode* pNode5 = new ComplexListNode();
pNode1->m_nValue = 1;
pNode2->m_nValue = 2;
pNode3->m_nValue = 3;
pNode4->m_nValue = 4;
pNode5->m_nValue = 5;
pNode1->m_pNext = pNode2;
pNode2->m_pNext = pNode3;
pNode3->m_pNext = pNode4;
pNode4->m_pNext = pNode5;
pNode5->m_pNext = nullptr;
pNode1->m_pSibling = pNode3;
pNode2->m_pSibling = pNode5;
pNode3->m_pSibling = nullptr;
pNode4->m_pSibling = pNode2;
pNode5->m_pSibling = nullptr;
ComplexListNode *pHead = Clone(pNode1);
cout << "反向打印新链表:" << endl;
printListReversingly_iteratively(pHead);
delete pNode1;
delete pNode2;
delete pNode3;
delete pNode4;
delete pNode5;
}