今天小編給大家分享一下Java復雜鏈表的復制方法是什么的相關知識點，內(nèi)容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設,沙依巴克企業(yè)網(wǎng)站建設,沙依巴克品牌網(wǎng)站建設,網(wǎng)站定制,沙依巴克網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,沙依巴克網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

    復雜鏈表的概念：

    在復雜鏈表中，每個結(jié)點除了有一個_pnext指針指向下一個結(jié)點外，還有一個_pSibling指向鏈表中的任意結(jié)點或者NULL。

  復雜鏈表每個結(jié)點的結(jié)構(gòu)如下：

    //復雜鏈表結(jié)點的結(jié)構(gòu)

    template

    struct ComplexListNode

    {

    ComplexListNode()

    :_pnext(NULL)

    ,_pSibling(NULL)

    { }

    ComplexListNode(const T& x)

    :_pnext(NULL)

    ,_pSibling(NULL)

    ,value(x)

    { }

    T value;//數(shù)據(jù)

    ComplexListNode* _pnext;//指向下一個結(jié)點

    ComplexListNode* _pSibling;//指向任意結(jié)點

    };

    復雜鏈表的復制：

    方法1：

    第一步，復制鏈表的每一個結(jié)點，并用_pnext鏈接起來；第二步，設置鏈表每一個結(jié)點的_pSibling。假設原始鏈表的某個結(jié)點N的_pSibling指向結(jié)點S，而S的位置可在N前也可在N后，所以要確定S的位置需要從頭結(jié)點開始找，若從頭開始沿著_pnext經(jīng)過s步找到S，那么復制鏈表上的N'結(jié)點的_pSibling離復制鏈表的頭結(jié)點的距離也是沿著_pnext指針s步。由于定位每個結(jié)點的_pSibling都需要從頭結(jié)點開始經(jīng)過O(n)步才能找到，所以時間復雜度為O(n^2)。比較浪費時間。

    方法2：

    第一步，復制鏈表的每一個結(jié)點，并用_pnext鏈接起來；第二步，設置每個結(jié)點的_pSibling。如果在原始鏈表的結(jié)點N的_pSibling指向結(jié)點S，那么復制鏈表時，對應的N'應該指向S'。因為有了哈希表，用O(1)的時間根據(jù)S找到S’。這種方法以空間換時間。

    方法3：

    第一步，對應于每一個結(jié)點，創(chuàng)建一個新的結(jié)點，并連接在原結(jié)點的后邊。

    參考代碼：

    //創(chuàng)建每個新的結(jié)點pCloned 分別連接到每個原結(jié)點的后邊

    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;

    }

    }

    第二步，設置復制出來結(jié)點的_pSibling，假設原始鏈表的A指向C，那么對應復制出來的A'對應C'。

    參考代碼：

    //設置復制出來每個結(jié)點的_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;

    }

    }

    第三步，拆分鏈表，奇數(shù)位置的結(jié)點用_pnext鏈接起來構(gòu)成原始鏈表，偶數(shù)位置的結(jié)點用_pnext鏈接起來構(gòu)成復制的復雜鏈表。

    參考代碼：

    //拆分合并的鏈表,把奇數(shù)位置上的結(jié)點用_pnext鏈接起來就是原始鏈表，把偶數(shù)位置上的結(jié)點用_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;

    }

    將以上三步合起來，就是復制的完整過程

    //復制復雜鏈表函數(shù)

    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復雜鏈表的復制方法是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文名稱：Java復雜鏈表的復制方法是什么-創(chuàng)新互聯(lián)
鏈接URL：http://news.spvevtbd.cn/article/dcgsid.html