剑指offer_面试题26_复杂链表的复制

小鱼儿 2022-08-04 04:27 146阅读 0赞

**题目：**请实现函数ComplexListNode \* Clone(ComplexListNode \* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个 m\_pNext 指针指向下一个结点外，还有一个 m\_pSibling 指向链表中的任意结点或者NULL。

**复杂链表结构定义如下：**

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

**方法一：**

**过程分析：**

1、第一步复制原始链表上的每一个结点，并用 m\_pNext 链接起来；

2、第二步设置每个结点的 m\_pSibling 指针。

**规律总结：**

1、由于 m\_pSibling 指针可能指向任意位置，因此需要有一个临时指针遍历，当遍历到的结点的数据 等于 m\_pSibling 指针 指向的结点的数据，说明临时指针指向的位置就是 新链表 m\_pSibling 指针 的值。不过前提是 链表中没有重复结点。

2、如有重复结点，则需要 记录 临时指针 走了多少步 才到原 m\_pSibling 指向的结点。然后复制链表也走这么多步。

时间复杂度：O（n^2）

**算法如下：**

/* 复制新的链表，使用了递归 */
    ComplexListNode* CloneNode_own(ComplexListNode *pHead)
    {
        if(NULL == pHead)
            return pHead;
    
        ComplexListNode *pCloned = new ComplexListNode;
        pCloned->m_nValue = pHead->m_nValue;
        pCloned->m_pSibling = NULL;
        pCloned->m_pNext = CloneNode_own(pHead->m_pNext);
    
        return pCloned;
    }
    
    /* 指定 m_pSibling,使用的是总结的规律1 */
    ComplexListNode* ConnectSiblingNodes_own(ComplexListNode *pHead,ComplexListNode *pClonedHead)
    {
        if(NULL == pHead || NULL == pClonedHead)
            return pClonedHead;
    
        ComplexListNode *pNode = pHead;
        ComplexListNode *pClonedNode = pClonedHead;
    
        while(pClonedNode != NULL)
        {
            if(pNode->m_pSibling != NULL)
            {
                ComplexListNode *temp = pClonedHead;     /**ComplexListNode *temp = pClonedNode; 不要这样写，因为m_pSibling可能指向前面*/
                while(temp->m_nValue != pNode->m_pSibling->m_nValue)
                {
                    temp = temp->m_pNext;
                }
                pClonedNode->m_pSibling = temp;
            }
            pClonedNode = pClonedNode->m_pNext;
            pNode = pNode->m_pNext;    /**这一步不要忘*/
        }
    
        return pClonedHead;
    }

**方法二：**

第一步：根据原始链表的每个结点 N 创建对应的 N' ，并且将 N' 接在 N 的后面。

![20150817212713955][]

第二步：设置复制出来的结点的 m\_pSibling 。假设原始链表上的 N 的 m\_pSibling 指向结点 S，那么其对应赋值出来的 N' 是 N 的 m\_pNext 指向的结点，同样 S' 也是 S 的 m\_pNext 指向的结点。

![20150817212729731][]

第三步：将两个链表拆分成两个链表。

![20150817212743173][]

**时间复杂度：O（n）**

**算法如下：**

/**第一步：复制原始链表的结点N并创建新结点N‘，再把N‘链接到N的后面*/
    void CloneNodes(ComplexListNode* pHead)
    {
        ComplexListNode* pNode = pHead;
        while(pNode != NULL)
        {
            ComplexListNode* pCloned = new ComplexListNode();
            pCloned->m_nValue = pNode->m_nValue;
            pCloned->m_pNext = pNode->m_pNext;
            pCloned->m_pSibling = NULL;
    
            pNode->m_pNext = pCloned;
    
            pNode = pCloned->m_pNext;
        }
    }
    
    /**第二步：设置赋值出来的结点的 m_pSibling */
    void ConnectSiblingNodes(ComplexListNode* pHead)
    {
        ComplexListNode* pNode = pHead;
        while(pNode != NULL)
        {
            ComplexListNode* pCloned = pNode->m_pNext;
            if(pNode->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 pClonedHead;
    }
    
    ComplexListNode* Clone(ComplexListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ReconnectNodes(pHead);
    }

**总结：**

这道题比较难理解，需要一步步分析，就比如方法二的第三步，需要有想象，一个拆线，连线的过程

/\* 点滴积累，我的一小步 \*/

[20150817212713955]: /images/20220731/4aafc479f3c3440b9baabaf7a235edb9.png
[20150817212729731]: /images/20220731/587f5b26f0584ca884fce63a64c746f0.png
[20150817212743173]: /images/20220731/1995acc890814300b17b7a9c566ef0f0.png