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 representingNode.valrandom_index: the index of the node (range from0ton-1) where random pointer points to, ornullif it does not point to any node.
Example 1:
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:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
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 <= 10000Node.randomis null or pointing to a node in the linked list.- Number of Nodes will not exceed 1000.
Solution: Hashtable
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua class Solution { public: Node* copyRandomList(Node* head) { if (!head) return head; unordered_map<Node*, Node*> m; Node* cur = m[head] = new Node(head->val); Node* ans = cur; while (head) { if (head->random) { auto it = m.find(head->random); if (it == end(m)) it = m.emplace(head->random, new Node(head->random->val)).first; cur->random = it->second; } if (head->next) { auto it = m.find(head->next); if (it == end(m)) it = m.emplace(head->next, new Node(head->next->val)).first; cur->next = it->second; } head = head->next; cur = cur->next; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment