剑指offer35-复杂链表的复制

原题(来源Leetcode)

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例 1:

剑指offer35-复杂链表的复制

输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出: [[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

剑指offer35-复杂链表的复制

输入: head = [[1,1],[2,1]] 输出: [[1,1],[2,1]]

示例 3:

剑指offer35-复杂链表的复制

输入: head = [[3,null],[3,0],[3,null]] 输出: [[3,null],[3,0],[3,null]]

示例 4:

输入: head = [] 输出: [] 解释: 给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

注意: 本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

解法

思想

我第一个想到的居然是Spring IOC解决循环依赖的思想。。先扫描一遍把节点都缓存下来,并用HashMap记录新旧节点的对应关系,然后再扫描一遍设置random节点。

代码

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node sentinel = new Node(0);
        Node curOld = head;
        Node curNew = sentinel;
        while(curOld!=null ){
            Node copy = new Node(curOld.val);
            curNew.next = copy;
            curNew = copy;
            map.put(curOld,copy);
            curOld = curOld.next;
        }
        for(Map.Entry<Node,Node> entry:map.entrySet()){
            Node old = entry.getKey();
            if(old.random != null)
                map.get(old).random = map.get(old.random);
        }
        return sentinel.next;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer35-%e5%a4%8d%e6%9d%82%e9%93%be%e8%a1%a8%e7%9a%84%e5%a4%8d%e5%88%b6/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月12日
下一篇 2020年6月14日

相关推荐

  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0120
  • leetcode72-编辑距离

    原题 给你两个单词 word1 和 word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字…

    2020年4月6日
    0140
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->…

    算法 2020年6月16日
    01380
  • leetcode121-买卖股票的最佳时机

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在…

    算法 2020年3月9日
    0120
  • leetcode648-单词替换

    原题 在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 oth…

    算法 2020年4月20日
    0150
  • leetcode14-最长公共前缀

    原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “…

    算法 2019年11月18日
    0110
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0130
  • leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates …

    2020年5月1日
    02750

发表回复

登录后才能评论