Leetcode : https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_28_copyRandomList/Solution.java
复制链表的复制
“题目描述 :请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。难度:中等
示例 1:
- 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
- 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
- 输入:head = [[1,1],[2,1]]
- 输出:[[1,1],[2,1]]
示例 3:
- 输入:head = [[3,null],[3,0],[3,null]]
- 输出:[[3,null],[3,0],[3,null]]
示例 4:
- 输入:head = []
- 输出:[]
- 解释:给定的链表为空(空指针),因此返回 null。
提示:
- 10000 <= Node.val <= 10000
- Node.random 为空(null)或指向链表中的节点。
- 节点数目不超过 1000 。
方法:哈希表
“利用哈希表的查询特点,考虑构建原链表节点和新链表对应节点的键值对映射关系,再遍历构建新链表各节点的next 和random 引用指向即可。
算法流程:
- 若头节点head为空节点,直接返回null ;
- 初始化:哈希表dic ,节点cur 指向头节点;
-
复制链表:
- 建立新节点,并向dic添加键值对(原cur节点,新cur节点) ;
- cur 遍历至原链表下一节点;
-
构建新链表的引用指向:
- 构建新节点的next 和random 弓|用指向;
- cur 遍历至原链表下一节点;
- 返回值:新链表的头节点dic[cur] ;
复杂度分析:
- 时间复杂度O(N) :两轮遍历链表,使用O(N)时间。
- 空间复杂度0(N) :哈希表dic 使用线性大小的额外空间。
- package com.nateshao.sword_offer.topic_28_copyRandomList;
- import java.util.HashMap;
- import java.util.Map;
- /**
- * @date Created by 邵桐杰 on 2021/12/2 14:05
- * @微信公众号 程序员千羽
- * @个人网站 www.nateshao.cn
- * @博客 https://nateshao.gitee.io
- * @GitHub https://github.com/nateshao
- * @Gitee https://gitee.com/nateshao
- * Description: 复杂链表的复制
- */
- public class Solution {
- /**
- * 精选解答
- * @param head
- * @return
- */
- public Node copyRandomList(Node head) {
- if(head == null) return null;
- Node cur = head;
-
Map
map = new HashMap<>(); - // 3. 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
- while(cur != null) {
- map.put(cur, new Node(cur.val));
- cur = cur.next;
- }
- cur = head;
- // 4. 构建新链表的 next 和 random 指向
- while(cur != null) {
- map.get(cur).next = map.get(cur.next);
- map.get(cur).random = map.get(cur.random);
- cur = cur.next;
- }
- // 5. 返回新链表的头节点
- return map.get(head);
- }
- /**
- * 思路:先复制链表的 next 节点,将复制后的节点接在原节点后,然后复制其它的
- * 节点,最后取偶数位置的节点(复制后的节点)。
- *
- * @param head
- * @return
- */
- public Node copyRandomList2(Node head) {
- if (head == null) return null;
- Node node = new Node(head.val);
- Node temp = node;
- while (head.next != null) {
- temp.next = new Node(head.next.val);
- if (head.random != null) {
- temp.random = new Node(head.random.val);
- }
- head = head.next;
- temp = temp.next;
- }
- return head;
- }
- // 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;
- }
- }
- }
参考链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-
原文链接:https://mp.weixin.qq.com/s/g5g2Hl3W84r-SjjfjG6DNg