[Leetcode] Copy list with random pointer 对带有任意指针的链表深度拷贝

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

深度复制：

仅简单的遍历一遍链表时，没法复制random pointer属性。所以有点懵，大神的做法如下，加入个人理解。

思路：对链表进行三次遍历。

第一次遍历复制每一个结点，将新结点接在原结点的后面，让链表变成一个重复链表，新旧交替；

第二次遍历维护新结点的随机指针，因，新结点是在旧结点之后，所以node->next->random=node->random->next，而node->node结点为新结点，这样，我们就把新结点的随机指针接好了；

第三次遍历，将两新旧结点分开，因为，构成的重复链表是新旧结点交替出现，故，只要每隔一个节点相连即可，就完成了对链表的分割。如下图：

 /**

  * Definition for singly-linked list with a random pointer.

  * struct RandomListNode {

  *     int label;

  *     RandomListNode *next, *random;

  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}

  * };

  */

 class Solution {

 public:

     RandomListNode *copyRandomList(RandomListNode *head)

     {

         if(head==NULL)  return NULL;

         //第一步，在oldNode的后面插入一个新的结点

         RandomListNode *oldNode=head;

         while(oldNode !=NULL)

         {

             RandomListNode *newNode=new RandomListNode(oldNode->label);

             newNode->next=oldNode->next;

             newNode->random=oldNode->random;

             oldNode->next=newNode;

             oldNode=newNode->next;  //遍历前行

         }    

         //第二步，关联random

         oldNode=head;

         while(oldNode !=NULL)

         {

             if(oldNode->random !=NULL)

                 oldNode->next->random=oldNode->random->next;

             oldNode=oldNode->next->next;

         }

         //第三步，分开两链表

         RandomListNode *newList=new RandomListNode();

         newList->next=head;

         RandomListNode *pHead=newList;

         oldNode=head;

         while(oldNode !=NULL)

         {

             pHead->next=oldNode->next;

             oldNode->next=pHead->next->next;

             pHead=pHead->next;

             oldNode=oldNode->next;

         }

         return newList->next;

     }

 };

巴特西

[Leetcode] Copy list with random pointer 对带有任意指针的链表深度拷贝

最新文章

热门文章