Leetcode138. 复制带随机指针的链表

复制带随机指针的链表

第一步拷贝节点链接在原节点的后面
第二步拷贝原节点的random ，拷贝节点的 random 在原节点 random 的 next
第三步将拷贝的节点尾插到一个新链表 ,并且将原链表恢复

从前往后遍历链表 ,将原链表的每个节点进行复制，并l链接到原节点的后面
malloc 一个节点copy

在这里插入图片描述

cur 往后走 ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了

第一步的代码

struct Node* copyRandomList(struct Node* head)
 {
	 struct Node * cur = head ;
     //cur 走到NULL 结束 
     while(cur)
     {
         struct Node * copy = ( struct Node *)malloc ( sizeof( stuct Node)); 
         //拷贝
         copy->val = cur->val;

         struct Node *  next = cur->next ;
         // 改变链接关系  cur copy next  
         cur->next =copy ;
         copy->next = next ;
         //cur 往后走  ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 
         cur = next ;

     }
}

对原链表 random 指针的复刻 , 即原节点的 random 拷贝到拷贝节点的 random 里面

在这里插入图片描述

原节点 13的random指针指向原节点 7 ,拷贝的新节点 13的random指针也需要指向拷贝的节点7
如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL

第二步的代码


       //处理拷贝节点的random 
       while(cur)
       {
            struct Node * copy = cur->next ;
           if(cur->random  == NULL)
           {
               copy->random = NULL ;//如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL
           }
           else 
           {
               copy->random = cur->random->next ;// 对原链表 random 指针的复刻
           }
           cur = cur->next->next ;
       }

在这里插入图片描述

上图中，我们可以观察到原节点 13的random指针指向原节点 7，拷贝的新节点13的random指针指向的是原节点7的next

推广一下也就是说
原节点 i 的random指针，指向的是原节点 j
那么新拷贝的节点的random指针,指向的是原节点 j 的 next

但是这样下来已经破坏了原链表，所以下一步是将拷贝的节点尾插到一个新链表 ,并且将原链表恢复

尾插
在这里插入图片描述

恢复原链表
在这里插入图片描述

第三步代码

    //将拷贝的新节点尾插到一个新链表, 并恢复原链表
          cur =head ;
       
        struct Node * copyhead  = NULL , * copyTail = NULL ;
       while( cur)
       {   
              struct Node *   copy =cur->next ;
          struct Node * next = copy->next ; 
                    //尾插
                if( copyhead ==NULL)
                {
                    copyhead = copyTail = copy ;
                }
                else
                {
                    copyTail->next = copy ;
                    copyTail = copyTail->next ;
                }
                //恢复原链表
                cur->next = next ;
                cur = next ;
       }

完整代码

struct Node* copyRandomList(struct Node* head)
 {
	 struct Node * cur = head ;
     //cur 走到NULL 结束 
     while(cur)
     {
         struct Node * copy = ( struct Node *)malloc ( sizeof( struct Node)); 
         //拷贝
         copy->val = cur->val;

         struct Node *  next = cur->next ;
         // 改变链接关系  cur copy next  
         cur->next =copy ;
         copy->next = next ;
         //cur 往后走  ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 
         cur = next ;

     }
       cur = head ;
       
       //处理拷贝节点的random 
       while(cur)
       {
            struct Node * copy = cur->next ;
           if(cur->random  == NULL)
           {
               copy->random = NULL ;
           }
           else 
           {
               copy->random = cur->random->next ;//
           }
           cur = cur->next->next ;
       }
       //将拷贝的新节点尾插到一个新链表, 并恢复原链表
          cur =head ;
       
        struct Node * copyhead  = NULL , * copyTail = NULL ;
       while( cur)
       {   
              struct Node *   copy =cur->next ;
          struct Node * next = copy->next ; 
                    //尾插
                if( copyhead ==NULL)
                {
                    copyhead = copyTail = copy ;
                }
                else
                {
                    copyTail->next = copy ;
                    copyTail = copyTail->next ;
                }
                //恢复原链表
                cur->next = next ;
                cur = next ;
       }
   return  copyhead ;
   
}