首页 > 其他分享 >复杂链表的复刻

复杂链表的复刻

时间:2023-04-04 11:35:39浏览次数:43  
标签:dummy head ListNode 复杂 random next 链表 tail 复刻

暴力做法

时间复杂度 O (n^2)

  1. 遍历一遍,复制 next 指针,新建链表
  2. 遍历第二遍,复制 random 指针,查找每一个 random 节点的位置
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        ListNode* dummy=new ListNode (-1),*tail=dummy;
        if(!head)   return dummy->next;
        //遍历一遍,复制next指针
        for(auto p=head;p;p=p->next)
            tail=tail->next=new ListNode(p->val);
        //遍历第二遍,复制random指针
        tail=dummy->next;
        for(auto p=head;p;p=p->next,tail=tail->next)
            if(p->random)//从头开始寻找random指针指向的地方
            {
                auto t=dummy->next,t2=head;//t和t2分别指向新旧链表
                while(t2!=p->random)//两指针同时往后走,直到找到random
                {
                    t=t->next;
                    t2=t2->next;
                }
                tail->random=t;
            }
        return dummy->next;
    }
};

哈希做法

暴力复杂度主要用于查找 random 节点,我们可以哈希存储原链表和新链表节点的对应关系,实现O (1) 查找

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        ListNode* dummy=new ListNode (-1),*tail=dummy;
        if(!head)   return dummy->next;
        unordered_map<ListNode*,ListNode*> hashtable;
        //遍历一遍,复制next指针,同时记录新旧链表节点的对应关系
        for(auto p=head;p;p=p->next)
        {
            tail=tail->next=new ListNode(p->val);
            hashtable[p]=tail;
        }
        //遍历第二遍,复制random指针
        tail=dummy->next;
        for(auto p=head;p;p=p->next,tail=tail->next)
            if(p->random)
                tail->random=hashtable[p->random];
                
        return dummy->next;
    }
};

标签:dummy,head,ListNode,复杂,random,next,链表,tail,复刻
From: https://www.cnblogs.com/tangxibomb/p/17285812.html

相关文章

  • 最长连续序列(并查集、数组)、复原 IP 地址(字符串、回溯)、删除链表的倒数第 N 个结
    最长连续序列(并查集、数组)给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)__的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4......
  • 环形链表
    给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如果pos......
  • 带环的单链表追击之拓展证明
    对于单链表有环问题,上一期,我们已经详细讲解了!!而快慢指针功不可没!!对于本期我们再次回顾,链表有环问题时,不难心中存在一个疑问,一定能追得上吗?会不会错过??那么为什么??为何能追上,什么情况下会追不上!!这就是我们今天讨论的重点!!假设单链表有环,快指针每次走两步,而慢指针每次走一步!!那么,快慢指......
  • PL/SQL 基础---复杂数据类型和自定义类型
    原文地址:https://blog.csdn.net/villare/article/details/53437924PL/SQL基础—复杂数据类型和自定义类型PLSQL中常用的自定义类型就两种:记录类型、PLSQL内存表类型(根据表中的数据字段的简单和复杂程度又可分别实现类似于简单数组和记录数组的功能)除此之外,还有大对象类型:CLOB......
  • 23. 合并 K 个升序链表
    题目描述给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。解题1/**2*Definitionforsingly-linkedlist.3*publicclassListNode{4*intval;5*ListNodenext;6*ListNo......
  • 全网最详细中英文ChatGPT-GPT-4示例文档-复杂函数快速转单行函数从0到1快速入门——官
    目录Introduce简介setting设置Prompt提示Sampleresponse回复样本APIrequest接口请求python接口请求示例node.js接口请求示例curl命令示例json格式示例其它资料下载ChatGPT是目前最先进的AI聊天机器人,它能够理解图片和文字,生成流畅和有趣的回答。如果你想跟上AI时代的潮流......
  • 114.二叉树展开为链表 Java
    114.二叉树展开为链表给你二叉树的根结点root,请你将它展开为一个单链表:展开后的单链表应该同样使用TreeNode,其中right子指针指向链表中下一个结点,而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。示例1:输入:root=[1,2,5,3,4,null,6]输出......
  • 力扣---剑指 Offer 36. 二叉搜索树与双向链表
    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例:   我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对......
  • go复杂数据类型 结构体
    前言:Go语言中没有“类”的概念,也不支持“类”的继承等面向对象的概念。通过结构体的方式来实现了面向对象,去除了传统的oop语法,继承,重载,构造,析构,隐藏this的特性,仍然有面向对象三大特性,实现和面向对象方法有所不同,没有extends关键字,结构体的内嵌配合接口比面向对象具有更......
  • 160. 相交链表
    160.相交链表给你两个单链表的头节点 headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null。图示两个链表在节点c1开始相交:题目数据保证整个链式结构中不存在环。注意,函数返回结果后,链表必须保持其原始结构。自定义评测:......