Java复杂链表的复制方法是什么-创新互联

今天小编给大家分享一下Java复杂链表的复制方法是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

创新互联建站是一家集网站建设,沙依巴克企业网站建设,沙依巴克品牌网站建设,网站定制,沙依巴克网站建设报价,网络营销,网络优化,沙依巴克网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

    复杂链表的概念：

    在复杂链表中，每个结点除了有一个_pnext指针指向下一个结点外，还有一个_pSibling指向链表中的任意结点或者NULL。

  复杂链表每个结点的结构如下：

    //复杂链表结点的结构

    template

    struct ComplexListNode

    {

    ComplexListNode()

    :_pnext(NULL)

    ,_pSibling(NULL)

    { }

    ComplexListNode(const T& x)

    :_pnext(NULL)

    ,_pSibling(NULL)

    ,value(x)

    { }

    T value;//数据

    ComplexListNode* _pnext;//指向下一个结点

    ComplexListNode* _pSibling;//指向任意结点

    };

    复杂链表的复制：

    方法1：

    第一步，复制链表的每一个结点，并用_pnext链接起来；第二步，设置链表每一个结点的_pSibling。假设原始链表的某个结点N的_pSibling指向结点S，而S的位置可在N前也可在N后，所以要确定S的位置需要从头结点开始找，若从头开始沿着_pnext经过s步找到S，那么复制链表上的N'结点的_pSibling离复制链表的头结点的距离也是沿着_pnext指针s步。由于定位每个结点的_pSibling都需要从头结点开始经过O(n)步才能找到，所以时间复杂度为O(n^2)。比较浪费时间。

    方法2：

    第一步，复制链表的每一个结点，并用_pnext链接起来；第二步，设置每个结点的_pSibling。如果在原始链表的结点N的_pSibling指向结点S，那么复制链表时，对应的N'应该指向S'。因为有了哈希表，用O(1)的时间根据S找到S’。这种方法以空间换时间。

    方法3：

    第一步，对应于每一个结点，创建一个新的结点，并连接在原结点的后边。

    参考代码：

    //创建每个新的结点pCloned 分别连接到每个原结点的后边

    template

    void ClonedNodes(ComplexListNode* pHead)

    {

    ComplexListNode* pNode = pHead;

    while (pNode != NULL)

    {

    ComplexListNode* pCloned = new ComplexListNode(pNode->value);

    pCloned->_pnext = pNode->_pnext;

    pNode->_pnext = pCloned;

    pNode = pCloned->_pnext;

    }

    }

    第二步，设置复制出来结点的_pSibling，假设原始链表的A指向C，那么对应复制出来的A'对应C'。

    参考代码：

    //设置复制出来每个结点的_pSibling的值

    template

    void ConnectSiblingNodes(ComplexListNode* pHead)

    {

    ComplexListNode* pNode = pHead;

    while (pNode)

    {

    ComplexListNode* pCloned = pNode->_pnext;

    if(pNode->_pSibling != NULL)

    {

    pCloned->_pSibling = pNode->_pSibling->_pnext;

    }

    pNode = pCloned->_pnext;

    }

    }

    第三步，拆分链表，奇数位置的结点用_pnext链接起来构成原始链表，偶数位置的结点用_pnext链接起来构成复制的复杂链表。

    参考代码：

    //拆分合并的链表,把奇数位置上的结点用_pnext链接起来就是原始链表，把偶数位置上的结点用_pnext链接起来就是复制出来的链表

    template

    ComplexListNode* ReconnectNodes(ComplexListNode* pHead)

    {

    ComplexListNode* pNode = pHead;

    ComplexListNode* pClonedHead = NULL;

    ComplexListNode* pClonedNode = NULL;

    if(pNode != NULL)

    {

    pClonedHead = pClonedNode = pHead->_pnext;

    pNode->_pnext = pClonedNode->_pnext;

    pNode = pNode->_pnext;

    }

    while (pNode != NULL)

    {

    pClonedNode->_pnext = pNode->_pnext;

    pClonedNode = pClonedNode->_pnext;

    pNode->_pnext = pClonedNode->_pnext;

    pNode = pNode->_pnext;

    }

    return pClonedHead;

    }

    将以上三步合起来，就是复制的完整过程

    //复制复杂链表函数

    template

    ComplexListNode* Clone(ComplexListNode* pHead)

    {

    ClonedNodes(pHead);

    ConnectSiblingNodes(pHead);

    return ReconnectNodes(pHead);

    }

    测试代码如下：

    void test()

    {

    ComplexListNode List1(1.2);

    ComplexListNode List2(1.4);

    ComplexListNode List3(2.3);

    ComplexListNode List4(3.6);

    ComplexListNode List5(4.5);

    List1._pnext = &List2;

    List2._pnext = &List3;

    List3._pnext = &List4;

    List4._pnext = &List5;

    List1._pSibling = &List3;

    List4._pSibling = &List2;

    List2._pSibling = &List5;

    ComplexListNode* pHead = Clone(&List1);

    }

以上就是“Java复杂链表的复制方法是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注创新互联行业资讯频道。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文标题：Java复杂链表的复制方法是什么-创新互联
转载源于：http://cdiso.cn/article/dcgsid.html