【剑指】复杂链表的复制

灰太狼 2023-06-25 10:11 9阅读 0赞

**题目描述**  
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

**思路：** 1，常规思路：先复制好next的链表，然后依次遍历，每一个节点的任意指点节点的寻找确定都会遍历一遍。O（n^2)  
2, 利用哈希表来节约时间，将每一个节点的对应的任意值节点存入入数组节点， 然后再复制新的。O（n）  
3，不用哈希也可以O（n）的方式：

分成三步：

**首先**，在每一个节点的后面复制一个同样节点，但是任意指向节点为null。  
此时我们就将整个链表变为  
| 一| 1 | 二 | 2 | 三 | 3 | 四 | 4 |。。。。。。  
待出结果链表每一个节点都在原链表的后一个节点。  
**然后**，复制他们的任意指向，**重点：！任意节点的后一个节点，就是复制节点任意指向节点！**  
**最后** 拆分两个链表：首先给出一个要返回的首节点。循环并判断当前节点为空否，不为，克隆的节点的next节点，复制为源节点的next节点，源节点后移一位，此时判断：当前源节点为空吗？不为空，将源节点next节点改为clone节点的下一节点（因为源节点下一个节点本来就是空，假如源节点此时为空）。

代码：

RandomListNode* Clone(RandomListNode* pHead)
        { 
            //一部分
            if(!pHead)    return nullptr;	//排除首节点为空
           clonelist(pHead);
           changesequence(pHead);
            return Reconnectlist(pHead);
        }
        
    private:
        void clonelist( RandomListNode*  pNode)
        { 
             RandomListNode*  node=pNode;
            while(node!=nullptr)
            { 
                 RandomListNode* pClone= new  RandomListNode(node->label);
                 //new一个新地址的节点（只有值的节点，无前无后）
                 RandomListNode*  next=node->next;
                 
                node->next= pClone;
                pClone->next=next;
                //插入一个节点，并改变指向
                node=pClone->next;
            }
            return;
        }
        //复制后的节点格式：原，克隆，原，克隆。。。所以，克隆点一定在原后面
        void  changesequence( RandomListNode* phead)
        { 
             RandomListNode* pnode=phead;
            while(pnode!=nullptr)
            { 
                 RandomListNode* pClone=pnode->next;	//新建一个指针地址不同，指向相同的一个节点
                 if(pnode->random!=nullptr)
                     pClone->random=pnode->random->next;
                     //精华在于任意指向的节点下一个节点是他本身的复制
                pnode=pnode->next->next;
            }
            
        }
        
        //第三部分，拆分成两个链表
         RandomListNode* Reconnectlist(  RandomListNode* phead)
        { 
             RandomListNode* pclonehead=phead->next;	//克隆的首节点
              RandomListNode* pnode=phead;
             while(pnode!=nullptr)
             { 
                  RandomListNode* clone=pnode->next;	//克隆可变节点
                 pnode->next=clone->next;//本来的克隆next下一个节点（源节点）
                 pnode=pnode->next;			//
                 if(pnode!=nullptr)			
                 //排除最后一个节点情况，上面已经连上了源节点的最后一个节点
                     clone->next=pnode->next;    //避免只有一个节点情况
             }
            return pclonehead;
        }