面试题26：复杂链表的复制

题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead),复制一个复杂链表。在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个Sibling指向链表中的任意结点或者NULL。结点的C++定义如下：

struct ComplexListNode{
    int value;
    int ComplexListNode* next;
    int ComplexListNode* Sibling;
    ComplexListNode(int data=int()):value(data),next(NULL),Sibling(NULL)
    {}
    ComplexListNode(const ComplexListNode& s):next(NULL),sibling(NULL)
    {
        value=s.value;
    }

};

分析

很容易想到的办法是先像普通链表一样将该链表中的每个结点复制出来，不考虑Sibling指针。然后第二遍复制Sibling指针即可。在遍历到每一个结点时，都从链表头再次遍历，找到当前结点的Sibling结点，同时修改复制出来的链表的对应结点的Sibling指针。

这种方法的时间复杂度达到了O(n²)，很明显不是最优的解法。

我们考虑这样一种思路：即复制的时候，将复制出来的结点挂在源结点的后面。比如原来链表是1,2,3,4,5，经过这一步后链表结点成了1,1,2，2,3,3,4,4,5,5.这样做的好处是复制Sibling指针时只需要O(1)的时间。即源结点的Sibling的next就是当前结点的Sibling。最后将复制出来的结点从源链表中分离出来即可。

代码如下：

ComplexListNode* Clone(ComplexListNode* head)
{
    if(head==NULL)
        return NULL;
    ComplexListNode* cur=head;
    ComplexListNode* tmp=head;
    ComplexListNode* newhead=NULL;;
    ComplexListNode* newtail=NULL;
    while(cur!=NULL)
    {
        tmp=cur->next;
        cur->next=new ComplexListNode(cur->value);
        cur=cur->next;
        cur->next=tmp;
        cur=cur->next;
    }
    cur=head;
    while(cur!=NULL)
    {
        tmp=cur->next;
        if(cur->sibling!=NULL)
            tmp->sibling=cur->sibling->next;
        cur=cur->next;
        cur=cur->next;
    }
    cur=head;
    newhead=newtail=cur->next;
    while(cur!=NULL)
    {
        cur->next=newtail->next;
        cur=cur->next;
        if(cur!=NULL)
        {
            newtail->next=cur->next;
            newtail=newtail->next;
        }
    }
    return newhead;
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往