// 面试题35:复杂链表的复制 // 题目:请实现函数ComplexListNode* Clone(ComplexListNode* pHead),复 // 制一个复杂链表。在复杂链表中,每个结点除了有一个m_pNext指针指向下一个 // 结点外,还有一个m_pSibling 指向链表中的任意结点或者nullptr。 #include <cstdio> #include "ComplexList.h" void CloneNodes(ComplexListNode* pHead); void ConnectSiblingNodes(ComplexListNode* pHead); ComplexListNode* ReconnectNodes(ComplexListNode* pHead); ComplexListNode* Clone(ComplexListNode* pHead) { CloneNodes(pHead); ConnectSiblingNodes(pHead); return ReconnectNodes(pHead); } 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; //下一位 } } 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; //下一位 } } ComplexListNode* ReconnectNodes(ComplexListNode* pHead) //断开连接 { ComplexListNode* pNode = pHead; ComplexListNode* pClonedHead = nullptr; ComplexListNode* pClonedNode = nullptr; if (pNode != nullptr) //设置头节点 { pClonedHead = pNode->m_pNext; //复制序列头节点 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; }
// ====================测试代码==================== void Test(const char* testName, ComplexListNode* pHead) { if (testName != nullptr) printf("%s begins:\n", testName); printf("The original list is:\n"); PrintList(pHead); ComplexListNode* pClonedHead = Clone(pHead); printf("The cloned list is:\n"); PrintList(pClonedHead); } // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | | /|\ /|\ // --------+-------- | // ------------------------- void Test1() { ComplexListNode* pNode1 = CreateNode(1); ComplexListNode* pNode2 = CreateNode(2); ComplexListNode* pNode3 = CreateNode(3); ComplexListNode* pNode4 = CreateNode(4); ComplexListNode* 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() { ComplexListNode* pNode1 = CreateNode(1); ComplexListNode* pNode2 = CreateNode(2); ComplexListNode* pNode3 = CreateNode(3); ComplexListNode* pNode4 = CreateNode(4); ComplexListNode* 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() { ComplexListNode* pNode1 = CreateNode(1); ComplexListNode* pNode2 = CreateNode(2); ComplexListNode* pNode3 = CreateNode(3); ComplexListNode* pNode4 = CreateNode(4); ComplexListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, nullptr); BuildNodes(pNode2, pNode3, pNode4); BuildNodes(pNode3, pNode4, nullptr); BuildNodes(pNode4, pNode5, pNode2); Test("Test3", pNode1); } // 只有一个结点 void Test4() { ComplexListNode* 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; }测试代码
#pragma once struct ComplexListNode { int m_nValue; ComplexListNode* m_pNext; ComplexListNode* m_pSibling; }; ComplexListNode* CreateNode(int nValue); void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling); void PrintList(ComplexListNode* pHead);ComplexList.h
#include <cstdio> #include "ComplexList.h" ComplexListNode* CreateNode(int nValue) { ComplexListNode* pNode = new ComplexListNode(); pNode->m_nValue = nValue; pNode->m_pNext = nullptr; pNode->m_pSibling = nullptr; return pNode; } void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling) { if(pNode != nullptr) { pNode->m_pNext = pNext; pNode->m_pSibling = pSibling; } } void PrintList(ComplexListNode* pHead) { ComplexListNode* pNode = pHead; while(pNode != nullptr) { printf("The value of this node is: %d.\n", pNode->m_nValue); if(pNode->m_pSibling != nullptr) printf("The value of its sibling is: %d.\n", pNode->m_pSibling->m_nValue); else printf("This node does not have a sibling.\n"); printf("\n"); pNode = pNode->m_pNext; } }ComplexList.cpp
分析:第三个函数交替变换来提供位置。
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { CloneNodes(pHead); ConnectSiblingNodes(pHead); return ReconnectNodes(pHead); } void CloneNodes(RandomListNode* pHead) { RandomListNode* pNode = pHead; while(pNode != nullptr) { //这里不新建节点就会出错 RandomListNode* pCloned = new RandomListNode(pNode->label); pCloned->label = pNode->label; pCloned->next = pNode->next; pCloned->random = nullptr; pNode->next = pCloned; pNode = pCloned->next; } } void ConnectSiblingNodes(RandomListNode* pHead) { RandomListNode* pNode = pHead; while(pNode != nullptr) { RandomListNode* pCloned = pNode->next; if (pNode->random != nullptr) pCloned->random = pNode->random->next; pNode = pCloned->next; } } RandomListNode* ReconnectNodes(RandomListNode* pHead) { RandomListNode* pNode = pHead; RandomListNode* pClonedHead = nullptr; RandomListNode* pClonedNode = nullptr; if (pNode != nullptr) { pClonedHead = pNode->next; pClonedNode = pNode->next; pNode->next = pClonedNode->next; pNode = pNode->next; } while (pNode != nullptr) { pClonedNode->next = pNode->next; pClonedNode = pClonedNode->next; pNode->next = pClonedNode->next; pNode = pNode->next; } return pClonedHead; } };牛客网提交代码