Nav: << previous: 137.只出现一次的数字 II | next: 139.单词拆分 >>
Description
tab: English
<p>A linked list of length <code>n</code> is given such that each node contains an additional random pointer, which could point to any node in the list, or <code>null</code>.</p>
<p>Construct a <a href="https://en.wikipedia.org/wiki/Object_copying#Deep_copy" target="_blank"><strong>deep copy</strong></a> of the list. The deep copy should consist of exactly <code>n</code> <strong>brand new</strong> nodes, where each new node has its value set to the value of its corresponding original node. Both the <code>next</code> and <code>random</code> pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. <strong>None of the pointers in the new list should point to nodes in the original list</strong>.</p>
<p>For example, if there are two nodes <code>X</code> and <code>Y</code> in the original list, where <code>X.random --> Y</code>, then for the corresponding two nodes <code>x</code> and <code>y</code> in the copied list, <code>x.random --> y</code>.</p>
<p>Return <em>the head of the copied linked list</em>.</p>
<p>The linked list is represented in the input/output as a list of <code>n</code> nodes. Each node is represented as a pair of <code>[val, random_index]</code> where:</p>
<ul>
<li><code>val</code>: an integer representing <code>Node.val</code></li>
<li><code>random_index</code>: the index of the node (range from <code>0</code> to <code>n-1</code>) that the <code>random</code> pointer points to, or <code>null</code> if it does not point to any node.</li>
</ul>
<p>Your code will <strong>only</strong> be given the <code>head</code> of the original linked list.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/12/18/e1.png" style="width: 700px; height: 142px;" />
<pre>
<strong>Input:</strong> head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
<strong>Output:</strong> [[7,null],[13,0],[11,4],[10,2],[1,0]]
</pre>
<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/12/18/e2.png" style="width: 700px; height: 114px;" />
<pre>
<strong>Input:</strong> head = [[1,1],[2,1]]
<strong>Output:</strong> [[1,1],[2,1]]
</pre>
<p><strong class="example">Example 3:</strong></p>
<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/12/18/e3.png" style="width: 700px; height: 122px;" /></strong></p>
<pre>
<strong>Input:</strong> head = [[3,null],[3,0],[3,null]]
<strong>Output:</strong> [[3,null],[3,0],[3,null]]
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>0 <= n <= 1000</code></li>
<li><code>-10<sup>4</sup> <= Node.val <= 10<sup>4</sup></code></li>
<li><code>Node.random</code> is <code>null</code> or is pointing to some node in the linked list.</li>
</ul>
> [!tip]- Hint 1
>
> Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, ensure you are not making multiple copies of the same node.
> [!tip]- Hint 2
>
> You may want to use extra space to keep old_node ---> new_node mapping to prevent creating multiple copies of the same node.
> [!tip]- Hint 3
>
> We can avoid using extra space for old_node ---> new_node mapping by tweaking the original linked list. Simply interweave the nodes of the old and copied list. For example:
Old List: A --> B --> C --> D
InterWeaved List: A --> A' --> B --> B' --> C --> C' --> D --> D'
> [!tip]- Hint 4
>
> The interweaving is done using next</b> pointers and we can make use of interweaved structure to get the correct reference nodes for random</b> pointers.
---
[submissions](https://leetcode.com/problems/copy-list-with-random-pointer/submissions/) | [solutions](https://leetcode.com/problems/copy-list-with-random-pointer/solutions/)
tab: 中文
<p>给你一个长度为 <code>n</code> 的链表，每个节点包含一个额外增加的随机指针 <code>random</code> ，该指针可以指向链表中的任何节点或空节点。</p>
<p>构造这个链表的 <strong><a href="https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin" target="_blank">深拷贝</a></strong>。 深拷贝应该正好由 <code>n</code> 个 <strong>全新</strong> 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 <code>next</code> 指针和 <code>random</code> 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。<strong>复制链表中的指针都不应指向原链表中的节点 </strong>。</p>
<p>例如，如果原链表中有 <code>X</code> 和 <code>Y</code> 两个节点，其中 <code>X.random --> Y</code> 。那么在复制链表中对应的两个节点 <code>x</code> 和 <code>y</code> ，同样有 <code>x.random --> y</code> 。</p>
<p>返回复制链表的头节点。</p>
<p>用一个由 <code>n</code> 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 <code>[val, random_index]</code> 表示：</p>
<ul>
<li><code>val</code>：一个表示 <code>Node.val</code> 的整数。</li>
<li><code>random_index</code>：随机指针指向的节点索引（范围从 <code>0</code> 到 <code>n-1</code>）；如果不指向任何节点，则为 <code>null</code> 。</li>
</ul>
<p>你的代码 <strong>只</strong> 接受原链表的头节点 <code>head</code> 作为传入参数。</p>
<p> </p>
<p><strong class="example">示例 1：</strong></p>
<p><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png" style="height: 142px; width: 700px;" /></p>
<pre>
<strong>输入：</strong>head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
<strong>输出：</strong>[[7,null],[13,0],[11,4],[10,2],[1,0]]
</pre>
<p><strong class="example">示例 2：</strong></p>
<p><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png" style="height: 114px; width: 700px;" /></p>
<pre>
<strong>输入：</strong>head = [[1,1],[2,1]]
<strong>输出：</strong>[[1,1],[2,1]]
</pre>
<p><strong class="example">示例 3：</strong></p>
<p><strong><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png" style="height: 122px; width: 700px;" /></strong></p>
<pre>
<strong>输入：</strong>head = [[3,null],[3,0],[3,null]]
<strong>输出：</strong>[[3,null],[3,0],[3,null]]
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>0 <= n <= 1000</code><meta charset="UTF-8" /></li>
<li><code>-10<sup>4</sup> <= Node.val <= 10<sup>4</sup></code></li>
<li><code>Node.random</code> 为 <code>null</code> 或指向链表中的节点。</li>
</ul>
<p> </p>
> [!tip]- 提示 1
>
> Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, ensure you are not making multiple copies of the same node.
> [!tip]- 提示 2
>
> You may want to use extra space to keep old_node ---> new_node mapping to prevent creating multiple copies of the same node.
> [!tip]- 提示 3
>
> We can avoid using extra space for old_node ---> new_node mapping by tweaking the original linked list. Simply interweave the nodes of the old and copied list. For example:
Old List: A --> B --> C --> D
InterWeaved List: A --> A' --> B --> B' --> C --> C' --> D --> D'
> [!tip]- 提示 4
>
> The interweaving is done using next</b> pointers and we can make use of interweaved structure to get the correct reference nodes for random</b> pointers.
---
[提交记录](https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/) | [题解](https://leetcode.cn/problems/copy-list-with-random-pointer/solution/)
Solutions & Notes
properties:
note.updated:
displayName: Last Updated
note.relative_links:
displayName: Related Links
note.desc:
displayName: Description
note.grade:
displayName: Rating
note.program_language:
displayName: Language
note.time_complexity:
displayName: TC
note.space_complexity:
displayName: SC
views:
- type: table
name: Solutions & Notes
filters:
and:
- file.hasLink(this.file)
- file.tags.containsAny("leetcode/solution", "leetcode/note")
order:
- file.name
- desc
- program_language
- time_complexity
- space_complexity
- grade
- relative_links
- updated
sort:
- property: grade
direction: ASC
- property: time_complexity
direction: ASC
- property: program_language
direction: ASC
columnSize:
file.name: 104
note.space_complexity: 65
note.grade: 126
Similar Problems
properties:
note.lcTopics:
displayName: Topics
note.lcAcRate:
displayName: AC Rate
note.favorites:
displayName: Favorites
note.grade:
displayName: Rating
note.translatedTitle:
displayName: Title (CN)
note.lcDifficulty:
displayName: Difficulty
views:
- type: table
name: Similar Problems
filters:
and:
- file.hasLink(this.file)
- similarQuestions.contains(this.file)
order:
- file.name
- translatedTitle
- lcTopics
- lcDifficulty
- lcAcRate
- grade
- favorites
sort:
- property: file.name
direction: ASC
- property: lcTopics
direction: DESC
columnSize:
note.translatedTitle: 240
note.lcTopics: 347
note.lcAcRate: 75
note.grade: 122