剑指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日

相关推荐

  • 剑指offer64-求1+2+…+n

    原题(来源Leetcode) 求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例1…

    算法 2020年6月2日
    0550
  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    080
  • leetcode289-生命游戏

    原题 根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞…

    算法 2020年4月2日
    0280
  • leetcode103-二叉树的锯齿形层次遍历

    原题 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树: [3,9,20,null,nul…

    算法 2020年1月25日
    060
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0140
  • leetcode450-删除二叉搜索树中的节点

    原题 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一…

    2020年1月16日
    080
  • 剑指offer13-机器人的运动范围

    原题(来源Leetcode) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下…

    算法 2020年4月8日
    0110
  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员,在面试中(不是) 难免会遇到海量数据相关的问题,之前有注意过java.util下面有一个BitSet数据结构,但不是很明白是做什么用的。今天就来研究一下它背…

    算法 2020年2月27日
    03360
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    080
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0220

发表回复

登录后才能评论