深度拷贝小解

本文简单的求解了一个链表深度拷贝的例子。

深拷贝和浅拷贝对应，浅拷贝是拷贝一引用，而深拷贝拷贝的不仅仅是引用，还包括引用所属的值，简单的说就是拷贝另一份。

题目：

深拷贝一个链表，链表除了含有next指针外，还包含一个random指针，该指针指向链表中的某个节点或者为空。

本题有两种思路，分别介绍下。

思路一：（图片来源于网络）

假设原始链表如下，细线表示next指针，粗线表示random指针，没有画出的指针均指向NULL：

构建新节点时，指针做如下变化，即把新节点插入到相应的旧节点后面：

代码：

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;

         /*第一遍扫描:对每个结点进行复制，把复制出来的新结点插在原结点之后*/

             RandomListNode* node = head;

             while(node != NULL)

             {

                 RandomListNode* newnode = new RandomListNode(node->label);

                 newnode->next = node->next;

                 node->next = newnode;

                 node = newnode->next;

             }

            /*第二遍扫描:根据原结点的random,给新结点的random赋值*/

             node = head;

             while(node != NULL)

             {

                  if(node->random != NULL)

                  {

                       node->next->random = node->random->next;

                  }

                  node = node->next->next;

             }

             RandomListNode* newhead = head->next;

             /*第三遍扫描:把新结点从原链表中拆分出来*/

             inode = head;

             while(node != NULL)

             {

                RandomListNode* newnode = node->next;

                node->next = newnode->next;

                if(newnode->next != NULL)

                     newnode->next = newnode->next->next;

                node = node->next;

             }

             return newhead;

        }

};

思路二：

该思路是利用两个HashMap来求解的，第一次遍历时：一个Map存放 旧值--新值 键值对、另一个Map存放 新值--旧值 键值对；第二次遍历时：将原链表中的random结点拷贝过来；看了代码就十分明了了。

代码：（java代码）

class Solution{

    public RandomListNode copyRandomList(RandomListNode head)

    {

       if(head == null) return head;

       /*新建一个链表的头结点*/

       RandomListNode newHead = new RandomListNode(head.label);

       RandomListNode oldp = head;

       RandomListNode newp = newHead;

       Map<RandomListNode,RandomListNode> map1 = new HashMap<RandomListNode,RandomListNode>();

       Map<RandomListNode,RandomListNode> map2 = new HashMap<RandomListNode,RandomListNode>();

        map1.put(newp,oldp);

        map2.put(oldp,newp);

        /*对旧链表进行复制*/

       oldp = head->next;

       while(oldp != null)

       {

          RandomListNode temp = new RandomListNode(oldp.label);

          map1.put(temp,oldp);

          map2.put(oldp,temp);

          newp.next = temp;

          newp = newp.next;

          oldp = oldp.next;

       }

       /*将Random指针进行复制*/

       newp = newHead;

       while(newp != null)

       {

         newp.random = map2.get(map1.get(newp).random);

     /*

                map1.get(newp):

         为新链表的结点对应旧链表中的旧结点;

                map1.get(newp).random:

        为旧结点的random;

                map2.get(map1.get(newp).random):

        为新结点的random;

        上述等式成立是因为新结点的random与对应旧结点的random也互为键值对

      */

         newp = newp.next;

       }

       return newHead;

   }

};

至此，两种思路介绍完毕。