leetcode138 || 链表 || 中等

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

 

示例 1:

leetcode138 || 链表 || 中等

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

leetcode138 || 链表 || 中等

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

leetcode138 || 链表 || 中等

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

示例 4:

输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。

 

提示:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。

 

先搞清楚概念,深拷贝:将对象所持有的资源一并拷贝

我的题解:

这道题思路很明确,我们在不断浅拷贝构造的同时,再把next和random指针指向的位置明确了,就完成了深拷贝

所以我们不妨理解为原链表为父亲链表,原链表中的node为父亲node,父亲node拷贝出来的node为其儿子node;

一个父亲node的next指向原链表中的下一个node,random指向原链表中定义的随机给定的一个node;

一个儿子node的next指向由其父亲node的next拷贝出来的儿子node,一个儿子node的random指向其父亲node的random拷贝出来的儿子node;

 

方法:顺序遍历父亲链表,根据每个父亲结点创建出儿子结点

 

建立父亲和儿子之间的映射关系,用父亲作为索引能获得其拷贝出来的儿子(哈希);

一边构建一边按顺序连接儿子结点;(明确next)

对父亲的random哈希一下,就能找到父亲的random拷贝出来的儿子了,也就是当前儿子结点的random应该指向的位置;(明确random)

class Solution {
public:
    Node* copyRandomList(Node* head) {
      unordered_map<Node*, Node*> Hash;
     //处理头结点
      Node* copy_node_head = new Node(head->val);
      Node* tmp_copy_node = copy_node_head;
      tmp_copy_node->random = head->random;
      Hash[head] = tmp_copy_node;

      Node * tmp = head->next;
      while (tmp != nullptr){
          Node* copy_node = new Node(tmp->val);//新建node
          tmp_copy_node->next = copy_node;//上一个新建的node指向当前新建的node
          Hash[tmp] = copy_node;//创建当前node和其父亲node的哈希
          copy_node->random = tmp->random;//将当前node的random指向其父亲node的random
          tmp_copy_node = copy_node;//当前node成为临时node
          tmp = tmp->next;
      }

      tmp = copy_node_head;
      while (tmp != nullptr){
          tmp->random = Hash[tmp->random];
          tmp = tmp->next;
      }
      return copy_node_head;
  }
};

 

太难看了?我也觉得,直接进行一个规的递!

class Solution {
private:
    unordered_map<Node*, Node*> mp;
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        if (mp.count(head)) return mp[head];
        Node* newHead = new Node(head->val);
        mp[head] = newHead;
        newHead->next = copyRandomList(head->next);
        newHead->random = copyRandomList(head->random);
        return newHead;
    }
};

简单、易读、快乐~

 

 

leetcode138 || 链表 || 中等

上一篇:两个链表的第一个公共节点


下一篇:leetcode 合并两个有序链表 简单