题解 | #复杂链表的复制#

方法一：哈希表

• 1.使用一个哈希表来映射原节点和新节点
• 2.通过将原节点和新节点的键值对添加进去代表当前节点已经复制
• 3.利用next和random的指向递归遍历链表

  代码如下：

  class Solution {
  public:
    unordered_map<RandomListNode*, RandomListNode*> hash;
    RandomListNode* Clone(RandomListNode* pHead) {
        //当前为空或者当前节点已复制，结束当前递归循环。
        if(pHead==nullptr)
            return nullptr;
        if(hash.count(pHead))
            return hash[pHead];
        //复制链表节点
        RandomListNode* newNode=new RandomListNode(pHead->label);
        hash[pHead]=newNode;
        //进入next和random的递归
        newNode->next=Clone(pHead->next);
        newNode->random=Clone(pHead->random);
        return newNode;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，链表节点数n，遍历。
  空间复杂度：O(n)，哈希表，最大值为所有节点都加入时，为O(n)。

方法二：

• 遍历链表，在每个节点的后一位复制节点，然后再将复制的节点提取出来组成新链表。

  图示如下:

  

  class Solution {
  public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead==nullptr)
            return nullptr;
        RandomListNode* cur=pHead;
        //复制节点到该节点后一个位置，包含next
        while(cur){
            RandomListNode* newNode=new RandomListNode(cur->label);
            RandomListNode* nextNode=cur->next;
            newNode->next=nextNode;
            cur->next=newNode;
            cur=nextNode;
        }
        //对复制后的节点设置其random值。
        cur=pHead;
        while(cur){
            if(cur->random)
                cur->next->random=cur->random->next;
            else
                cur->next->random=nullptr;
            cur=cur->next->next;
        }
        //单独提取出复制后的节点组成新链表
        cur=pHead;
        RandomListNode* newHead=pHead->next;
        RandomListNode* newTail=newHead;
        while(cur){
            cur->next=cur->next->next;
            cur=cur->next;
            //表尾cur为空的情况
            newTail->next = cur ? cur->next : nullptr; 
            newTail = newTail->next;
        }
        return newHead;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，遍历链表两次。
  空间复杂度：O(1)，除结果所需的节点外仅常量个临时变量。