Leetcode Copy List with Random Pointer（面试题推荐）

给大家推荐一道leetcode上的面试题，这道题的具体讲解在《剑指offer》的P149页有思路讲解，如果你手头有这本书，建议翻阅。

题目链接 here

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.

RandomList中，每个节点不光有一个next指针，而且每个链表节点都有一个random指针，随机指向链表中的一个节点，让你复制这个链表，节点的C++定义如下。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 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) {}
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
  
 

     看到这个题目，估计很多人的第一反应是，先把这个单链表复制出来，然后挨个找random指向的节点。仔细想想这样效率很低，复制链表很快，但确定每个节点的random指针就不容易了，用这种方法的话，每找一个random指针，都必须遍历一次链表。时间复杂度O(n^2)。

    可能也有人可能会想到时间换空间的方法，用hash把时间复杂度降到O(n)。

    当然，还有更省时省空间的方法。

     大概思路就是，在原链表的基础上，把每个节点复制一份加的原来节点的后面，然后设置好新节点random指针，在把所有的新节点从原链表中分离出来，构成一个新链表，这个链表就是我们要的原链表的拷贝。

    下面有三个函数，第一个明显就是复制新节点并把其加入到被复制节点的后面。第二个，因为新节点的random指针还是指向旧节点的，要把它指向新节点，很简单，因为每个节点的新节点都是在原来的节点之后的。 第三个函数，把新节点从原链表中抽离，构成一个新链表。

   这种方法的好处就是，时间复杂度只有O(n)，而且我们不需要额外的空间。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    void CloneNode(RandomListNode *head) {
     
    
   

    

     

    
    

     

              RandomListNode * p = head;
     
    
   

    

     

    
    

     
        while (NULL != p) {
     
    
   

    

     

    
    

     

                  RandomListNode * CloneNode = new RandomListNode(p->label);
     
    
   

    

     

    
    

     

                  CloneNode->next = p->next;
     
    
   

    

     

    
    

     

                  CloneNode->random = p->random;
     
    
   

    

     

    
    

     

                  p->next = CloneNode;
     
    
   

    

     

    
    

     

                  p = CloneNode->next;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    void ConnectRandomNode(RandomListNode * head) {
     
    
   

    

     

    
    

     

              RandomListNode * p = head;
     
    
   

    

     

    
    

     
        while (NULL != p) {
     
    
   

    

     

    
    

     

                  RandomListNode *pclone = p->next;
     
    
   

    

     

    
    

     
            if (NULL != pclone->random) {
     
    
   

    

     

    
    

     

                      pclone->random = pclone->random->next;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

                  p = pclone->next;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    RandomListNode *copyRandomList(RandomListNode *head) {
     
    
   

    

     

    
    

     
        if (NULL == head)
     
    
   

    

     

    
    

     
            return head;
     
    
   

    

     

    
    

     
        CloneNode(head);
     
    
   

    

     

    
    

     
        ConnectRandomNode(head);
     
    
   

    

     

    
    

     

              RandomListNode *pnode = head;
     
    
   

    

     

    
    

     

              RandomListNode *pclonehead = pnode->next;
     
    
   

    

     

    
    

     

              RandomListNode *pclonenode = pnode->next;
     
    
   

    

     

    
    

     
        while (NULL != pnode) {
     
    
   

    

     

    
    

     

                  pnode->next = pclonenode->next;
     
    
   

    

     

    
    

     

                  pnode = pnode->next;
     
    
   

    

     

    
    

     
            if (NULL != pnode){
     
    
   

    

     

    
    

     

                       pclonenode->next = pnode->next;
     
    
   

    

     

    
    

     

                       pclonenode = pclonenode->next;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return pclonehead;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/38311479