復雜鏈表的復制——26

    實現函數ComplexListNode* Clone(ComplexListNode* pHead)，復制一個復雜鏈表。在復雜鏈表中，每個結點除了有一個m_pNext的指針指向下一個結點外，還有一個m_pSibling的指針指向鏈表中任意結點或者NULL。

如下如所示的一個復雜鏈表，沒有畫出_sib指針的結點表示_sib指向NULL：

   對于復雜鏈表的復制，首先可以想到的是先遍歷一遍鏈表復制出各個結點并設置好_next指針，復制好單向的鏈表之后，對于_sib的隨機指針則需要每一次都從頭遍歷找出距當前結點多遠的結點才是應該指向的隨機結點，雖然可行，但不難發現這樣尋找隨機結點的時間復雜度是O(N*N)；

    首先，有一種方法，仍然是先遍歷鏈表創建出相應的結點并設置好每一個的_next指針，之后用一個哈希桶來保存每一個原鏈表結點的地址和新創建出結點的地址信息，也就是在每一個原鏈表結點地址的下面鏈上新創建出對應的鏈表結點的地址，這樣的話一次就能定位新復制出鏈表中每一個結點的_sib應該指向哪一個對應的結點了；雖然時間復雜度降為了O(N)，但這是一種以空間換時間的方法；

    另外的一種方法，是在遍歷到原鏈表的一個結點的時候，就新創建出一個結點插入當前結點的后面，完成之后原鏈表就變成了兩個連續重復的結點的雙倍長度的鏈表，這樣的話，原來鏈表中結點的_sib后面的重復的結點，也就會是新創建鏈表對應結點的_sib的指向，之后再從頭訪問鏈表，將原鏈表中每個結點對應的_sib指針后面的結點賦值給當前結點后面新創建結點的_sib，這樣也就完成了新建鏈表的_sib指向，之后再將兩個鏈表拆開就可以了；

程序設計如下：

#include <iostream>
#include <assert.h>
using namespace std;

int list_num = 0;

struct ComplexListNode//復雜鏈表結點數據結構
{
    int _val;
    ComplexListNode* _next;
    ComplexListNode* _sib;

    ComplexListNode(int val)//構造函數
        :_val(val)
         ,_next(NULL)
         ,_sib(NULL)
    {}  
};

ComplexListNode* Buy_Node(int val)//構建復雜鏈表結點
{
    ComplexListNode* node = new ComplexListNode(val);
    return node;
}

//插入結點
void Push_Node(ComplexListNode** phead, int val)
{
    if((*phead) == NULL)
        (*phead) = Buy_Node(val);
    else
    {   
        ComplexListNode* tmp = (*phead);
        while(tmp->_next != NULL)
            tmp = tmp->_next;
        tmp->_next = Buy_Node(val);
    }

    ++list_num;
}

//設置自由結點的指向
void SetSibPointer(ComplexListNode* head, int* positions)
{
    assert(head && positions);

    ComplexListNode* tmp = head;
    ComplexListNode *p[list_num];
    for(size_t i = 0; i < list_num; ++i)
    {
        p[i] = tmp;
        tmp = tmp->_next;
    }

    tmp = head;
    for(size_t i = 0; i < list_num; ++i)
    {
        if(positions[i] != 0)
            tmp->_sib = p[positions[i]];

        tmp = tmp->_next;
    }
}

//銷毀鏈表
void DestoryList(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode* tmp = head;
        while(head != NULL)
        {
            head = head->_next;
            delete tmp;
            tmp = NULL;
            tmp = head;
        }
    }
}

//打印鏈表
void PrintList(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode *tmp = head;
        while(tmp != NULL)
        {
            cout<<tmp->_val<<"->";
            tmp = tmp->_next;
        }
        cout<<"NULL"<<endl;

        tmp = head;
        while(tmp != NULL)
        {
            cout<<tmp->_val<<" sibling is ->";
            if(tmp->_sib != NULL)
                cout<<tmp->_sib->_val<<endl;
            else
                cout<<"NULL"<<endl;

            tmp = tmp->_next;
        }
    }
}

//復制復雜鏈表
ComplexListNode* Clone(ComplexListNode* head)
{
    if(head != NULL)
    {
        ComplexListNode *tmp = head;
        ComplexListNode *newnode = NULL;

        //復制每個結點并插入當前結點的后面
        while(tmp != NULL)
        {
            newnode = Buy_Node(tmp->_val);
            newnode->_next = tmp->_next;
            tmp->_next = newnode;
            tmp = newnode->_next;
        }

        //設置新創建鏈表結點的sib指針的指向
        tmp = head;
        newnode = tmp->_next;
        while(tmp != NULL)
        {
            if(tmp->_sib != NULL)
                newnode->_sib = tmp->_sib->_next;
            tmp = newnode->_next;
            if(tmp != NULL)
                newnode = tmp->_next;
        }
        //拆分兩個鏈表
        tmp = head;
        ComplexListNode* NewHead = tmp->_next;
        newnode = tmp->_next;
        while(tmp != NULL)
        {
            tmp->_next = newnode->_next;
            tmp = tmp->_next;
            if(tmp != NULL)
            {
                newnode->_next = tmp->_next;
                newnode = newnode->_next;
            }
        }

        return NewHead;
    }
}

int main()
{
    ComplexListNode* head = NULL;
    Push_Node(&head, 7);
    Push_Node(&head, 5);
    Push_Node(&head, 8);
    Push_Node(&head, 2);
    Push_Node(&head, 6);
    Push_Node(&head, 9);
    Push_Node(&head, 3);

    int positions[7] = {2,5,0,4,0,0,4};
    SetSibPointer(head, positions);
    cout<<"Complex List: ";
    PrintList(head);
     ComplexListNode* NewComplexListHead = Clone(head);
    cout<<"New Complex List: ";
    PrintList(NewComplexListHead);
    cout<<"Complex List: ";
    PrintList(head);

    DestoryList(head);
    DestoryList(NewComplexListHead);
    return 0;
}

運行程序：

《完》