温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java复杂链表的复制方法是什么

发布时间:2022-01-10 09:36:45 来源:亿速云 阅读:186 作者:iii 栏目:编程语言

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

    复杂链表的概念:

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

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

    //复杂链表结点的结构

    template<class T>

    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<class T>

    void ClonedNodes(ComplexListNode<T>* pHead)

    {

    ComplexListNode<T>* pNode = pHead;

    while (pNode != NULL)

    {

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

    pCloned->_pnext = pNode->_pnext;

    pNode->_pnext = pCloned;

    pNode = pCloned->_pnext;

    }

    }

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

    参考代码:   

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

    template<class T>

    void ConnectSiblingNodes(ComplexListNode<T>* pHead)

    {

    ComplexListNode<T>* pNode = pHead;

    while (pNode)

    {

    ComplexListNode<T>* pCloned = pNode->_pnext;

    if(pNode->_pSibling != NULL)

    {

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

    }

    pNode = pCloned->_pnext;

    }

    }

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

    参考代码:   

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

    template<class T>

    ComplexListNode<T>* ReconnectNodes(ComplexListNode<T>* pHead)

    {

    ComplexListNode<T>* pNode = pHead;

    ComplexListNode<T>* pClonedHead = NULL;

    ComplexListNode<T>* 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<class T>

    ComplexListNode<T>* Clone(ComplexListNode<T>* pHead)

    {

    ClonedNodes<T>(pHead);

    ConnectSiblingNodes<T>(pHead);

    return ReconnectNodes<T>(pHead);

    }

    测试代码如下:    

    void test()

    {

    ComplexListNode<double> List1(1.2);

    ComplexListNode<double> List2(1.4);

    ComplexListNode<double> List3(2.3);

    ComplexListNode<double> List4(3.6);

    ComplexListNode<double> 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<double>* pHead = Clone(&List1);

    }

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

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI