Skip to content

Latest commit

 

History

History
100 lines (70 loc) · 2.68 KB

0138-copy-list-with-random-pointer.adoc

File metadata and controls

100 lines (70 loc) · 2.68 KB
Raw

138. Copy List with Random Pointer

{leetcode}/problems/copy-list-with-random-pointer/[LeetCode - Copy List with Random Pointer^]

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val

  • random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

{image_attr} 
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

{image_attr} 
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

{image_attr} 
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

  • -10000 ⇐ Node.val ⇐ 10000

  • Node.random is null or pointing to a node in the linked list.

  • Number of Nodes will not exceed 1000.

思路分析

这道题可以使用类似 133. Clone Graph 的解法来求解。

{image_attr}
{image_attr}

新旧节点相连的解法非常精妙！

使用 Map 的解法也好巧妙啊！

一刷
link:{sourcedir}/_0138_CopyListWithRandomPointer.java[role=include]
二刷
link:{sourcedir}/_0138_CopyListWithRandomPointer_2.java[role=include]