首页 / 操作系统 / Linux / 复杂链表的复制

题目：有一个复杂链表，其结点除了有一个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. ", pNode->m_nValue）;
       
        if（pNode->m_pSibling ！= NULL）
            printf（"The value of its sibling is: %d. ", pNode->m_pSibling->m_nValue）;
        else
            printf（"This node does not have a sibling. "）;
       
        printf（" "）;
       
        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: "）;
    PrintList（pNode1）;    ComplexListNode*  pClonedHead = Clone（pNode1）;    printf（"The cloned list is: "）;
    PrintList（pClonedHead）;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/132847.htm