方法一:哈希表

  • 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),除结果所需的节点外仅常量个临时变量。