首页 > 代码库 > 剑指offer (27) 复杂链表的复制

剑指offer (27) 复杂链表的复制

2024-07-09 06:07:00   217人阅读

题目：请实现一个函数，复制一个复杂链表，在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点，还有一个m_pSibling指向链表中的任意节点或者NULL

struct ComplexListNode {    int              m_nValue;    ComplexListNode* m_pNext;    ComplexListNode* m_pSibling;};

 

方法一：

step1. 复制原始链表的每一个节点，并用m_pNext链接起来

step2. 设置每个结点的m_pSibling指针

由于m_pSibling指针可以指向任意结点，所以定位每个结点的m_pSibling指针都需要从原始链表的头结点开始找

定位每个结点的m_pSibling指针都需要O(n)遍历链表，所以该方法的时间复杂度为 O(n^2)

 

方法二：用空间换时间，使用一个大小为O(n)的哈希表，将方法一的查找操作从O(n)降为O(1)

step1. 复制原始链表的每一个节点N，创建对应结点N‘, 并用m_pNext链接起来,同时将<N, N‘>的配对信息放在一个哈希表中

step2. 如果原始链表中结点N的m_pSibling指向结点S，那么复制链表中，对应的N‘应该指向S‘ ，由于有哈希表，我们可以根据S找到S’

 

方法三：

 

void CloneNodes(ComplexListNode* pHead){    ComplexListNode* pNode = pHead;    while (pNode != NULL) {        ComplexListNode* pCloned = new ComplexListNode();        pCloned->m_nValue = http://www.mamicode.com/pNode->m_nValue;        pCloned->m_pNext = pNode->m_pNext;        pCloned->m_pSibling = NULL;        pNode->m_pNext = pCloned;        pNode = pCloned->m_pNext;    }}

 

 

void ConnectSiblings(ComplexListNode* pHead){    ComplexListNode* pNode = pHead;    while (pNode != NULL) {        ComplexListNode* pCloned = pNode->m_pNext;        if (m_pNext->m_pSibling != NULL) {            pCloned->m_pSibling = pNode->m_pSibling->m_pNext;        }        pNode = pCloned->m_pNext;    }}

 

  

ComplexListNode* ReconnectNodes(ComplexListNode* pHead){    ComplexListNode* pNode = pHead;    ComplexListNode* pClonedHead = NULL;    ComplexListNode* pClonedNode = NULL;    if (pNode != NULL) {        pClonedHead = pClonedNode = pNode->m_pNext;        pNode->m_pNext = pClonedNode->m_pNext;        pNode = pNode->m_pNext;    }    while (pNode != NULL) {        pClonedNode->m_pNext = pNode->m_pNext;        pClonedNode = pClonedNode->m_pNext;        pNode->m_pNext = pClonedNode->m_pNext;        pNode = pNode->m_pNext;    }    return pClonedNode;}

 


联系
我们