復雜鏈表的復制

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