復雜鏈表的復制

題目：請實現函數ComplexListNode* clone(ComplexListNode* pHead)，復制

一個復雜鏈表。在復雜鏈表中，每個節點除了有一個m_pNext指針指向下一個

節點外，還有以一個m_pSibling指向鏈表中的任意節點或者NULL。節點定義如下：

在complexList.h中定義

#pragma once
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);

#include"complexList.h"
#include "stdio.h"
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;
    }
}

#include
#include"complexList.h"
//復制原始鏈表的任意節點N並創建新節點N'，再把N'連接到N的後面。
void cloneNodes(ComplexListNode* pHead)
{
	if(pHead == NULL)
		return;

	ComplexListNode* pNode = pHead;
	while(pNode != NULL)
	{
		ComplexListNode* pCloned = new ComplexListNode();
		pCloned->m_pNext = pNode->m_pNext;
		pCloned->m_nValue = pNode->m_nValue;
		pCloned->m_pSibling = NULL;
		pNode->m_pNext = pCloned;
		pNode = pNode->m_pNext;
	}
}
//如果原始鏈表上的節點N的m_pSibling指向，則它對應的復制節點
//N'的m_pSibling指向S的下一節點S'。
void connectSiblingNodes(ComplexListNode* pHead)
{
	if(pHead == NULL)
		return;

	ComplexListNode* pNode = pHead;
	while(pNode != NULL)
	{
		if(pNode->m_pSibling)
		{
			pNode->m_pNext->m_pSibling = pNode->m_pSibling->m_pNext;
		}
		pNode = pNode->m_pNext;
	}
}
//將上面兩步得到的表拆分成兩個鏈表
ComplexListNode* reconnectNodes(ComplexListNode* pHead)
{
	ComplexListNode* pNode = pHead;
	ComplexListNode* pCLonedHead = NULL;
	ComplexListNode* pClonedNode = NULL;

	if(pHead)
	{
		pCLonedHead = pClonedNode = pNode->m_pNext;
		pNode->m_pNext = pClonedNode->m_pNext;
		pNode = pNode->m_pNext;
	}

	while(pNode != NULL)
	{
		pClonedNode->m_pNext = pNode->m_pNext;
		pNode->m_pNext = pClonedNode->m_pNext;
		pNode = pNode->m_pNext;
		pClonedNode = pClonedNode->m_pNext;
	}
	return pCLonedHead;
}
ComplexListNode* clone(ComplexListNode* pHead)
{
	cloneNodes(pHead);
	reconnectNodes(pHead);
	return reconnectNodes(pHead);
}

void test()
{
	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, pNode5);
    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);
}
int main()
{
	test();
}