復雜鏈表的復制

題目：有一個復雜鏈表，其結點除了有一個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);
}