剑指offer | 面试题28：复制链表的复制

千羽

发布于 2021-12-29 13:24:53

2090

发布于 2021-12-29 13:24:53

文章被收录于专栏：程序员千羽

死磕算法系列文章

“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

剑指 Offer 28. 复杂链表的复制

题目描述 ：请实现 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 指向头节点;
复制链表:
1. 建立新节点，并向dic添加键值对(原cur节点，新cur节点) ;
2. cur 遍历至原链表下一节点;
构建新链表的引用指向:
1. 构建新节点的next 和random 弓|用指向;
2. 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<Node, Node> 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-

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-06，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树