CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

    • 图理论基础
    • 图的搜索:DFS

      • 岛屿的最大面积:BFS 和 DFS 模板
      • 岛屿数量
      • 节点间通路
      • 二分图
      • 所有路径:需要存储路径的 DFS 模板
      • 单词搜索:DFS + 回溯模板
      • 计算除法
      • 最长递增路径:记忆化 DFS 模板
      • 二叉树中所有距离为 K 的结点
      • 克隆图
      • 剑指 Offer 17 - 打印从 1 到最大的 n 位数
      • 剑指 Offer 35 - 复杂链表的复制
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
      • 展平多级双向链表
    • 图的搜索:BFS

    • 拓扑排序

    • 并查集

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 图
  • 图的搜索:DFS
小牛肉
2022-10-07
目录

剑指 Offer 35 - 复杂链表的复制

# 📃 题目描述

题目链接:

  • 剑指 Offer 35. 复杂链表的复制 (opens new window)
  • 138. 复制带随机指针的链表 (opens new window)

# 🔔 解题思路

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        // 记录已经复制过的节点,key:原节点, value:复制的节点
        Map<Node, Node> copyed = new HashMap<>();
        Node newHead = dfs(head, copyed);
        return newHead;
    }

    // dfs 复制 node 链表, 并返回复制后链表的首节点
    private Node dfs(Node node, Map<Node, Node> copyed) {
        if (node == null) {
            return null;
        }

        if (!copyed.containsKey(node)) {
            Node newNode = new Node(node.val);
            copyed.put(node, newNode);
			
            // dfs 复制 node.next
            newNode.next = dfs(node.next, copyed);
            // dfs 复制 node.random
            newNode.random = dfs(node.random, copyed);
        }

        return copyed.get(node); 
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
剑指 Offer 17 - 打印从 1 到最大的 n 位数
展平多级双向链表

← 剑指 Offer 17 - 打印从 1 到最大的 n 位数 展平多级双向链表→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式