`
blue2048
  • 浏览: 182611 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Copy List with Random Pointer - java

 
阅读更多

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-leetcode题解之138-Copy-List-with-Random-Pointer

    python python_leetcode题解之138_Copy_List_with_Random_Pointer

    两两认识leetcode-copy-list-with-random-pointer:使用随机指针复制链表

    两两认识leetcode 使用随机指针复制链表 给出一个链表,使得每个节点都包含一个额外的随机指针,该指针可以指向链表中的任何节点或为空。 返回列表的深层副本。 链表在输入/输出中表示为 n 个节点的列表。 每个节点...

    LeetCode最全代码

    * [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-leetcode-java:leetcode上的题解,基于java语言

    每天刷点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 ...

    LeetCode:LeetCode解决方案

    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动态规划

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...

    dna匹配leetcode-leetcode:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring ...Pointer 单链表 map Max Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    Leetcode题目+解析+思路+答案.pdf

    - **Copy List with Random Pointer**:复制带有随机指针的链表。 8. **数学(Math)**: - **Reverse Integer**:反转一个整数。 9. **字符串(String)**: - **Add Binary**:将两个二进制数相加。 - **...

    leetcode-cpp刷题

    - **2.2.10 Copy List with Random Pointer** - 复制一个带随机指针的链表。 - 实现思路:先复制链表中的每个节点,并将其插入到原节点后面,然后再处理随机指针。 #### 五、编写规范 - **单一文件编码**:由于...

    leetcode java

    - 有难度的链表题目则要求合并K个有序链表(Merge K Sorted Lists)、复制带有随机指针的链表(Copy List with Random Pointer)。 **二叉树(Binary Tree)** 二叉树是另一个重要的数据结构。LeetCode的题目涵盖了...

    Leetcode答案(c++版)

    **1.10 Copy List with Random Pointer (138)** - **问题描述**:给定一个带有随机指针的链表,复制该链表。 - **解题思路**: - 遍历链表,在每个节点后面插入一个新节点。 - 再次遍历链表,更新新节点的随机...

    leetcode题库-pyshua:这是一个Python的编码判断系统

    leetcode题库 pyshua Python 算法题练习 用法: python Judge.py library problem 例子: python Judge.py leetcode TwoSum 如何贡献: 收录题库 LeetCode (还有4题未录入, 分别为 LRU Cache, Copy List with Random ...

    Leetcode book刷题必备

    24. Copy List with Random Pointer:复制带有随机指针的链表。 【二叉树】 25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree:计算二叉树的最大深度。 27. Minimum Depth of ...

    leetcode代码200题c++

    7. **Copy List with Random Pointer**:这是一个涉及链表和深度复制的复杂问题。需要理解链表结构,并能创建一个新的链表,同时保留原链表的随机指针。 8. **Word Ladder II**:这是一个词链问题,涉及到广度优先...

    LeetCode练习答案

    - **复制带随机指针的链表(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...

    lrucacheleetcode-CPPS:CPPS

    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 堆 ...

Global site tag (gtag.js) - Google Analytics