您现在的位置是:首页 > 正文

Leetcode 138. 复制带随机指针的链表 解题思路及C++实现

2024-04-01 05:26:36阅读 1

解题思路:

主要包括三步。

第一步是遍历一次链表,复制其每一个节点,并将所复制的节点接在其后。

第二步是遍历一次链表,解决拷贝节点的random指针的指向。

第三步是从这个大链表中,拆出原有链表和拷贝链表。

具体图解,课参考LeetCode官方图解。

 

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

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        Node* tmp = head;
        //遍历链表,复制每一个节点,并将其放在所复制节点之后
        while(tmp){
            Node* hh = new Node(tmp->val);
            hh->next = tmp->next;
            tmp->next = hh;
            tmp = hh->next;
        }
        tmp = head;
        //遍历链表,使得复制的节点的random指针指向正确的节点
        while(tmp){
            if(tmp->random == NULL) tmp->next->random = NULL;
            else tmp->next->random = tmp->random->next;
            if(tmp->next)
                tmp = tmp->next->next;
            else tmp = NULL;
        }
        Node* res = head->next;
        // tmp 记录原始的链表节点,tmp2记录新复制的链表节点
        tmp = head;   
        Node* tmp2 = head;
        while(tmp){
            tmp2 = tmp->next;
            tmp->next = tmp2->next;
            tmp = tmp->next;
            if(tmp) tmp2->next = tmp->next;
            else tmp2->next = NULL;
        }
        return res;
    }
};

 

 

 

网站文章

  • 如何发挥测试策略的指导性作用

    测试策略是保证测试过程有效开展、测试资源利用最大化、测试质量稳定可靠的重要前提,但是在实际研发过程中却往往会被忽略。很多时候会被认为是一项文档工作,从网站找一个文档改巴改巴应付了事。如果管理者对测试策略也不重视,可能会造成质量失控、工作无序、贻误战机等更大的损失。

    2024-04-01 05:26:27
  • 使用notepad++ 让word里面的代码高亮

    使用notepad++ 让word里面的代码高亮

    最近写项目总结文档,需要在word里面插入代码,为了让各种语言的代码都能在word里面高亮显示,就像在编辑器里面一样,在网上找到了这个方法。 首先需要notepad++,其实用的是它里面的一个插件,有些notepad++版本默认是没有插件的 然后打开notepad++ ,将你的代码粘贴至编辑器中,然后选择菜单栏的语言,选择你对应的语言。

    2024-04-01 05:25:48
  • Design compiler约束之——path_group

    Design compiler约束之——path_group

    今天发现了一个宝藏文档(这也反映出了我有多菜,这么晚才发现)synopsys官方的timing约束手册。通过官方文档中的描述来一起学习一下这个path group约束。设计的时序路径被组织成group的形式,默认情况下,设计中每个时钟域有一个path group。

    2024-04-01 05:25:41
  • Mysql 锁、事务强制手动kill/释放

    1、查看数据库当前的进程,看一下有无正在执行的慢SQL记录线程。 mysql> show processlist; 2、查看当前的事务 当前运行的所有事务 mysql> SELECT * FROM information_schema.INNODB_TRX; 当前出现的锁 mysql> SELECT * FROM information_schema.INNO...

    2024-04-01 05:25:34
  • Git入门和使用

    Git入门和使用

    git入门和简单的使用,在idea开发工具上面的使用

    2024-04-01 05:24:51
  • MySQL的核心日志

    MySQL的核心日志

    MySQL 中有七种日志文件,分别是:redo log(重做日志)、undo log(回滚日志)、bin log(二进制日志)、error log(错误日志)、slow query log(慢查询日志...

    2024-04-01 05:24:44
  • Linux6安装bind错误,CentOS 7.6环境下Bind 9的安装与配置

    Linux6安装bind错误,CentOS 7.6环境下Bind 9的安装与配置

    查看当前系统版本[root@iZj6cehstgjoj3qav88fidZ ~]# cat /etc/redhat-releaseCentOS Linux release 7.6.1810 (Core...

    2024-04-01 05:24:37
  • IDEA把jar包导入web项目同时能在运行时自动部署到tomcat

    IDEA把jar包导入web项目同时能在运行时自动部署到tomcat

    首先表示一下,我依然不太懂原理,完全是靠多次的尝试得出的结果,但是目前反复测试后看起来是完全实现了效果。 新建好web项目后在WEB-INFO文件夹下新建一个lib文件夹,在未导入jar包前,代码是有...

    2024-04-01 05:23:54
  • 尚硅谷大数据项目【电商数仓5.0】学习笔记

    尚硅谷大数据项目【电商数仓5.0】学习笔记

    尚硅谷大数据项目【电商数仓5.0】学习笔记

    2024-04-01 05:23:49
  • QT多媒体简单应用

    QT多媒体简单应用

    多媒体(Multimedia)是多种媒体的综合,一般包括文本,声音和图像等多种媒体形式。在计算机系统中,多媒体指组合两种或两种以上媒体的一种人机交互式信息交流和传播媒体。使用的媒体包括文字、图片、照片、声音、动画和影片,以及程式所提供的互动功能。Qt 的多媒体模块提供了音频、视频、录音、摄像头拍照和录像等功能。...

    2024-04-01 05:23:34