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

作者:神秘网友 发布时间:2021-02-28 13:50:04

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

问题

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

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

示例

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

解答1:哈希表

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_mapNode*, Node* ump;
        Node* cur = head;
        while (cur) {
            Node* node = new Node(cur-val);
            ump[cur] = node;
            cur = cur-next;
        }
        cur = head;
        while (cur) { // 新生成的节点通过哈希表建立关系
            ump[cur]-next = ump[cur-next];
            ump[cur]-random = ump[cur-random];
            cur = cur-next;
        }
        return ump[head];
    }
};

重点思路

链表的深拷贝问题,因为涉及random指针,可以将新建立的节点与原始节点通过哈希表建立一一对应关系。

解答2:拼接+拆分

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        Node* cur = head;
        while (cur) { // 链表复制阶段
            Node* node = new Node(cur-val);
            node-next = cur-next;
            cur-next = node;
            cur = node-next;
        }
        Node* res = head-next;
        cur = head;
        while (cur) { // random赋值阶段
            if (cur-random) cur-next-random = cur-random-next;
            cur = cur-next-next; // cur存在时cur-next一定存在
        }
        Node* pre = head;
        cur = pre-next;
        while (cur-next) { // 链表拆分阶段
            pre = pre-next = cur-next;
            cur = cur-next = pre-next;
        }
        pre-next = NULL;
        return res;
    }
};

重点思路

需要三次遍历:

  1. 在原始链表每一个后面复制一个新节点;
  2. 新节点重建random关系;
  3. 拆分为两个链表。

【剑指Offer-35】复杂链表的复制 相关文章

  1. 【剑指Offer-34】二叉树中和为某一值的路径

    问题 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例 解答 class Solution {public: vectorvectorint pathSum(TreeNode* root, int sum) { recur(root, sum);

  2. 【LeetCode】剑指 Offer 60. n个骰子的点数

    题目链接:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/ 本题使用动态规划 由于题目要求最后的结果是返回一个浮点型数组,因此首先需要明确当抛出n个骰子时,点数之和有多少种情况,由于每个骰子的值为 1~6 ,因此最小值为 n ,最大值为

  3. 【剑指Offer-33】二叉搜索树的后序遍历序列

    问题 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 示例 输入: [1,6,3,2,5] 输出: false 输入: [1,3,2,6,5] 输出: true 解答1:递归 class Solution {

  4. 时间空间(complexity)

    时间空间复杂度 时间复杂度: 通俗来说就是随着数据量的增加,程序运行的时间花费量是怎么变化的 , 时间复杂度常用大o表示。举个例子,猜数字,猜10个,100个、1000个,猜数的数据量是在增加的,但是实际运行程序花费的时间是怎么变化的呢,是线性的常数的

  5. 剑指 Offer 54. 二叉搜索树的第k大节点 树的遍历

    地址https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/ 给定一棵二叉搜索树,请找出其中第k大的节点。示例 1:输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3 5

  6. 剑指 Offer 52. 两个链表的第一个公共节点 哈希

    地址https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/ 输入两个链表,找出它们的第一个公共节点。如下面的两个链表: 在节点 c1 开始相交。 示例 1:输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,

  7. 剑指 Offer 33. 二叉搜索树的后序遍历序列

    剑指 Offer 33. 二叉搜索树的后序遍历序列 Difficulty: 中等 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树: 5 / \ 2 6 / \ 1 3

  8. [剑指offer] 复杂链表的复制

    题目 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。 示例 1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[1

  9. Spark对复杂结构的处理

    结构体 创建结构体 在字符串公式中就是一个”()“就表示一个结构体 //创建结构体 //方法1: df.selectExpr("(Description, InvoiceNo) as complex", "*").show(2) //方法2: df.selectExpr("struct(Description, InvoiceNo) as complex", "*").show(2) 查

  10. 【剑指Offer-20】表示数值的字符串

    问题 请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。 示例 字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。 解答1:确定有限状态自动机(DFA) class Solution

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词