学步园

76.复杂链表的复制
题目：有一个复杂链表,其结点除了有一个 m_pNext 指针指向下一个结点外，还有一个
m_pSibling指向链表中的任一结点或者 NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。

图中实线箭头表示 m_pNext指针，虚线箭头表示 m_pSibling  指针。为简单起见，指向 NULL 
的指针没有画出。请完成函数 ComplexNode* Clone(ComplexNode* pHead) ，以复制一个
复杂链表。

/*
76.复杂链表的复制
题目：有一个复杂链表,其结点除了有一个 m_pNext 指针指向下一个结点外，还有一个
m_pSibling指向链表中的任一结点或者 NULL。其结点的C++定义如下：
struct ComplexNode
{
	int m_nValue;
	ComplexNode* m_pNext;
	ComplexNode* m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示 m_pNext指针，虚线箭头表示 m_pSibling  指针。为简单起见，指向 NULL 
的指针没有画出。请完成函数 ComplexNode* Clone(ComplexNode* pHead) ，以复制一个
复杂链表。


首先复制每一个结点N为N*，不同的是我们将N*让在对应的N后面
然后我们要确定每一个N*的sibling分量，非常明显，N的sibling分量的next就是N*的sibling分量。
最后，将整个链表拆分成原始链表和拷贝出的链表。

*/ 
struct Node
{
    int val;
    Node* next;
    Node* sibling;
};

//第一步 
void Clone(Node* head)// 将N*链表复制到N后面 
{
    Node* current=head;
    while(current)
    {
        Node* temp=new Node;
        temp->val=current->val;
        temp->next=current->next;
        temp->sibling=NULL;
        
        current->next=temp;//将新复制的结点链接在原始结点的后面 
        current=temp->next;
    }
}
 

/*
第二步是设置我们复制出来的链表上的结点的m_pSibling。
假设原始链表上的N的m_pSibling指向结点S，那么其对应复制出来的N’是N->m_pNext，同样S’也是S->m_pNext。
*/ 
void ConstructSibling(Node* head)
{
    Node* origin=head;
    Node* clone;
    while(origin)
    {
        clone=origin->next;//复制的 
        
        if(origin->sibling)//原来的m_pSibling 
            clone->sibling=origin->sibling->next;
        origin=clone->next;
    }
}

/*
第三步是把这个长链表拆分成两个：把奇数位置的结点链接起来就是原始链表，
把偶数位置的结点链接出来就是复制出来的链表。
*/
Node* Split(Node* head)
{
    Node *CloneHead,*clone,*origin;
    origin=head;
    if(origin)
    {
        CloneHead=origin->next;
        
        origin->next=CloneHead->next;//原来的 
        origin=CloneHead->next;
        
        clone=CloneHead;
    }
    while(origin)
    {
        Node* temp=origin->next;
        
        origin->next=temp->next;//原来的
        origin=origin->next;
        
        clone->next=temp;
        clone=temp;
    }
    return CloneHead;
}

ComplexNode* Clone(ComplexNode* pHead)  
{ 
	//the whole thing
	Clone(head);
	ConstructSibling(head);
	return Split(head);
}