【剑指】35.复杂链表的复制

题目描述

请实现函数RandomListNode* Clone(RandomListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个random 指向链表中的任意结点或者nullptr。

算法分析

三步法(图源见水印)

哈希表法：首先遍历原链表，创建新链表（赋值label和next），用哈希表关联对应结点；再遍历一原链表，更新新链表的random指针。

提交代码：

class Solution { public: /* 三步法 */ RandomListNode* Clone(RandomListNode* pHead) { if (!pHead) return nullptr; RandomListNode* pNode = pHead; // 复制原始链表的任一节点并链接到该节点的后边 while (pNode) { RandomListNode* pTemp = new RandomListNode(pNode->label); pTemp->next = pNode->next; pNode->next = pTemp; pNode = pTemp->next; } // 初始化复制节点的random关系 pNode = pHead; while (pNode) { RandomListNode* pTemp = pNode->next; if(pNode->random) pTemp->random = pNode->random->next; pNode = pTemp->next; } // 从链表中拆分出新链表 RandomListNode* pCopyHead = pHead->next; RandomListNode* pCopyNode= pHead->next; pNode = pHead; while (pNode) { pNode->next = pCopyNode->next; if(pNode->next) pCopyNode->next = pNode->next->next; pNode = pNode->next; pCopyNode = pCopyNode->next; } return pCopyHead; } /* Hash表法 */ RandomListNode* Clone2(RandomListNode* pHead) { if (!pHead) return nullptr; map<RandomListNode*, RandomListNode*> nodeMap; RandomListNode* pNode = pHead; /* 创建结点 */ while (pNode) { RandomListNode* pTemp = new RandomListNode(pNode->label); nodeMap[pNode] = pTemp; pNode = pNode->next; } pNode = pHead; /* 创建连接关系 */ while (pNode) { RandomListNode* pTemp = nodeMap[pNode]; pTemp->next = nodeMap[pNode->next]; pTemp->random = nodeMap[pNode->random]; pNode = pNode->next; } return nodeMap[pHead]; } };

测试代码：

// ====================测试代码==================== void Test(const char* testName, RandomListNode* pHead) { if (testName != nullptr) printf("%s begins:\n", testName); printf("The original list is:\n"); PrintList(pHead); Solution s; RandomListNode* pClonedHead = s.Clone(pHead); printf("The cloned list is:\n"); PrintList(pClonedHead); } // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | | /|\ /|\ // --------+-------- | // ------------------------- void Test1() { RandomListNode* pNode1 = CreateNode(1); RandomListNode* pNode2 = CreateNode(2); RandomListNode* pNode3 = CreateNode(3); RandomListNode* pNode4 = CreateNode(4); RandomListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, pNode3); BuildNodes(pNode2, pNode3, pNode5); BuildNodes(pNode3, pNode4, nullptr); BuildNodes(pNode4, pNode5, pNode2); Test("Test1", pNode1); } // m_pSibling指向结点自身 // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | | /|\ /|\ // | | -- | // |------------------------| void Test2() { RandomListNode* pNode1 = CreateNode(1); RandomListNode* pNode2 = CreateNode(2); RandomListNode* pNode3 = CreateNode(3); RandomListNode* pNode4 = CreateNode(4); RandomListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, nullptr); BuildNodes(pNode2, pNode3, pNode5); BuildNodes(pNode3, pNode4, pNode3); BuildNodes(pNode4, pNode5, pNode2); Test("Test2", pNode1); } // m_pSibling形成环 // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | /|\ // | | // |---------------| void Test3() { RandomListNode* pNode1 = CreateNode(1); RandomListNode* pNode2 = CreateNode(2); RandomListNode* pNode3 = CreateNode(3); RandomListNode* pNode4 = CreateNode(4); RandomListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, nullptr); BuildNodes(pNode2, pNode3, pNode4); BuildNodes(pNode3, pNode4, nullptr); BuildNodes(pNode4, pNode5, pNode2); Test("Test3", pNode1); } // 只有一个结点 void Test4() { RandomListNode* pNode1 = CreateNode(1); BuildNodes(pNode1, nullptr, pNode1); Test("Test4", pNode1); } // 鲁棒性测试 void Test5() { Test("Test5", nullptr); } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; }