Java復雜鏈表的復制方法是什么

今天小編給大家分享一下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復雜鏈表的復制方法是什么”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。