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

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

    復雜鏈表的概念：

    在復雜鏈表中，每個結點除了有一個_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：

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

    參考代碼：

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

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

網站欄目：Java復雜鏈表的復制方法是什么-創(chuàng)新互聯
分享地址：http://weahome.cn/article/dcgsid.html