1. 第一次遍历深度克隆链表费random属性,并使用map记录一一对应的链表节点
2. 第二次遍历,根据map记录的节点关系, 补全random引用
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if(head==null){ return null; } Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>(); RandomListNode p = head; RandomListNode headNew = new RandomListNode(head.label); RandomListNode pNew = headNew; map.put(p, pNew); while (p != null){ RandomListNode next = p.next; if(next == null){ break; } RandomListNode nextNew = new RandomListNode(next.label); pNew.next = nextNew; p = p.next; map.put(next, nextNew); pNew = pNew.next; } p = head; pNew = headNew; while (p != null){ RandomListNode rand = p.random; RandomListNode randNew = map.get(rand); pNew.random = randNew; p = p.next; pNew = pNew.next; } return headNew; } }
相关推荐
python python_leetcode题解之138_Copy_List_with_Random_Pointer
两两认识leetcode 使用随机指针复制链表 给出一个链表,使得每个节点都包含一个额外的随机指针,该指针可以指向链表中的任何节点或为空。 返回列表的深层副本。 链表在输入/输出中表示为 n 个节点的列表。 每个节点...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium Remove Nth Node From End of List Swap Nodes in Pairs Spiral Matrix Path Sum II Copy List with Random ...
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...
dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring ...Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...
- **Copy List with Random Pointer**:复制带有随机指针的链表。 8. **数学(Math)**: - **Reverse Integer**:反转一个整数。 9. **字符串(String)**: - **Add Binary**:将两个二进制数相加。 - **...
- **2.2.10 Copy List with Random Pointer** - 复制一个带随机指针的链表。 - 实现思路:先复制链表中的每个节点,并将其插入到原节点后面,然后再处理随机指针。 #### 五、编写规范 - **单一文件编码**:由于...
- 有难度的链表题目则要求合并K个有序链表(Merge K Sorted Lists)、复制带有随机指针的链表(Copy List with Random Pointer)。 **二叉树(Binary Tree)** 二叉树是另一个重要的数据结构。LeetCode的题目涵盖了...
**1.10 Copy List with Random Pointer (138)** - **问题描述**:给定一个带有随机指针的链表,复制该链表。 - **解题思路**: - 遍历链表,在每个节点后面插入一个新节点。 - 再次遍历链表,更新新节点的随机...
leetcode题库 pyshua Python 算法题练习 用法: python Judge.py library problem 例子: python Judge.py leetcode TwoSum 如何贡献: 收录题库 LeetCode (还有4题未录入, 分别为 LRU Cache, Copy List with Random ...
24. Copy List with Random Pointer:复制带有随机指针的链表。 【二叉树】 25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree:计算二叉树的最大深度。 27. Minimum Depth of ...
7. **Copy List with Random Pointer**:这是一个涉及链表和深度复制的复杂问题。需要理解链表结构,并能创建一个新的链表,同时保留原链表的随机指针。 8. **Word Ladder II**:这是一个词链问题,涉及到广度优先...
- **复制带随机指针的链表(Copy List with Random Pointer)**: 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点,复制这个链表。 ##### 数学(Math) - **反转整数...
24. Copy List with Random Pointer:复制含有随机指针的链表。 四、二叉树 25. Validate Binary Search Tree:验证二叉搜索树的合法性。 26. Maximum Depth of Binary Tree:二叉树的最大深度。 27. Minimum Depth...
List_with_Random_Pointer.py) + 16 散列 + 17 散列 [A](./hash_table/Insert_Delete_GetRandom_O(1).py) + 18 大批 + 19 二分查找 + 20 DP —— 21 堆 —— 22 散列 + 23 DP + 24 DP —— 25 DP + 26 堆 + 27 堆 ...