HHot 100C++ 图解

138. 随机链表的复制

中等 链表 在力扣上做

一句话套路原地把 next 指向克隆结点,再拆两条链

题目描述

给你一个长度为 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:

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

示例 2:

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

示例 3:

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

 

提示:

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

 

思路

时间O(n)
空间O(n)

解法一(本文件采用)

两趟 + 哈希表 old->new。好懂、好讲。

解法二 O(1) 空间

先把 copy 插在 原结点 后面 A->A'->B->B',则 A'->random = A->random->next;最后再拆链。

图解

7 i0 13 i1 11 i2 10 i3 1 i4
链表结构(来自本仓库测试数据)

C++17 题解

src/07_linked_list.cpp48 行
namespace lc0138 {
class Solution {
 public:
  Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> mp;
    for (Node* p = head; p; p = p->next) mp[p] = new Node(p->val);  // 只复制值
    for (Node* p = head; p; p = p->next) {
      mp[p]->next = p->next ? mp[p->next] : nullptr;
      mp[p]->random = p->random ? mp[p->random] : nullptr;  // 指针映射过去
    }
    return head ? mp[head] : nullptr;
  }
};

// —— 测试脚手架:按下标数组构造随机链表 ——
inline Node* buildRandList(const vector<int>& vals, const vector<int>& randomIdx) {
  vector<Node*> nodes;
  for (size_t i = 0; i < vals.size(); ++i) nodes.push_back(new Node(vals[i]));
  for (size_t i = 0; i < nodes.size(); ++i) {
    if (i + 1 < nodes.size()) nodes[i]->next = nodes[i + 1];
    nodes[i]->random = randomIdx[i] < 0 ? nullptr : nodes[randomIdx[i]];
  }
  return nodes.empty() ? nullptr : nodes[0];
}
inline vector<int> randRandomIdx(Node* head, const vector<Node*>& orig) {
  vector<int> out;
  for (Node* p = head; p; p = p->next) {
    int idx = -1;
    for (size_t i = 0; i < orig.size(); ++i)
      if (orig[i] == p->random) idx = (int)i;
    out.push_back(idx);
  }
  return out;
}
inline vector<Node*> collect(Node* head) {
  vector<Node*> v;
  for (Node* p = head; p; p = p->next) v.push_back(p);
  return v;
}
// random 不影响 next 链,只顺着 next 释放即可(不会 double free)
inline void freeRandList(Node* head) {
  while (head) {
    Node* n = head->next;
    delete head;
    head = n;
  }
}
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q138_copy_random_list12 行
lc0138::Solution s;
Node* head = lc0138::buildRandList({7, 13, 11, 10, 1}, {-1, 0, 4, 2, 0});
Node* copy = s.copyRandomList(head);
CHECK_EQ(lc0138::collect(copy).size(), (size_t)5);  // 长度一致
CHECK_EQ(lc0138::randRandomIdx(copy, lc0138::collect(copy)),
         vector<int>{-1, 0, 4, 2, 0});  // random 相对结构一致
CHECK_TRUE(copy != head);               // 必须是新结点
CHECK_TRUE(copy->next != head->next);
Node* empty = s.copyRandomList(nullptr);
CHECK_TRUE(empty == nullptr);
lc0138::freeRandList(head);
lc0138::freeRandList(copy);

↑↓ 选择↵ 打开/ 随时唤起