复杂链表的复制

复杂链表的复制

题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：

struct ComplexNode

{

    int m_nValue;

    ComplexNode* m_pNext;

    ComplexNode* m_pSibling;

};

请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。

思路:分三步，在不用辅助空间的情况下实现O(n)的时间效率。第一步，复制原始链表的任意结点N并创建新结点N‘，再把N’链接到N的后面

第二步，如果原始链表的结点N的m_pSibling指向S，则它对应的复制结点N‘的m_pSibling指向S的下一结点S’

第三步，把这个链表拆分成两个链表

#include<stdio.h>
#include<iostream>
#include "stdafx.h"

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);

ComplexListNode* CreateNode(int nValue)
{
    ComplexListNode* pNode = new ComplexListNode();
   
    pNode->m_nValue = nValue;
    pNode->m_pNext = NULL;
    pNode->m_pSibling = NULL;
   
    return pNode;
}

void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling)
{
    if(pNode != NULL)
    {
        pNode->m_pNext = pNext;
        pNode->m_pSibling = pSibling;
    }
}

void PrintList(ComplexListNode* pHead)
{
    ComplexListNode* pNode = pHead;
    while(pNode != NULL)
    {
        printf("The value of this node is: %d.\n", pNode->m_nValue);
       
        if(pNode->m_pSibling != NULL)
            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;
    }
}

void CloneNodes(ComplexListNode* pHead);    //复制原始链表
void ConnectSiblingNodes(ComplexListNode* pHead); //设置复制出来的的结点的m_pSibling
ComplexListNode* ReconnectNodes(ComplexListNode* pHead);//拆分两个链表

ComplexListNode* Clone(ComplexListNode* pHead)
{
    CloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}

//第一步
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;
    }
}

//第二步
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;
}

//          -----------------
//        \|/              |
//  1-------2-------3-------4-------5
//  |      |      /|\            /|\
//  --------+--------              |
//          -------------------------

int main()
{
    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,  pNode4);
    BuildNodes(pNode3,  pNode4,  NULL);
    BuildNodes(pNode4,  pNode5,  pNode2);

    printf("The original list is:\n");
    PrintList(pNode1);

    ComplexListNode*  pClonedHead = Clone(pNode1);

    printf("The cloned list is:\n");
    PrintList(pClonedHead);
}

本文永久更新链接地址：