【力扣】138. 复制带随机指针的链表
发布日期:2021-06-29 19:46:24
浏览次数:2
分类:技术文章
本文共 1909 字,大约阅读时间需要 6 分钟。
题目:给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 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 <= 10000Node.random 为空(null)或指向链表中的节点。节点数目不超过 1000 。
答案:
/*// 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; }}*/class Solution { public Node copyRandomList(Node head) { /** 复制一个新的节点在原有节点之后,如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null 从头开始遍历链表,通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来,当然需要判断 cur.random 是否存在 将复制完的链表一分为二 */ if(head == null) return head; Node current = head; while(current != null){ Node copyNode = new Node(current.val); copyNode.next = current.next; current.next = copyNode; current = current.next.next; } current = head; while(current != null){ //判断原来节点有没有random指针 if(current.random != null) current.next.random = current.random.next; current = current.next.next; } //一分为二 Node copyHead = head.next; current = head; Node curCopy = head.next; while(current != null){ current.next = current.next.next; current = current.next; if(curCopy.next != null){ curCopy.next = curCopy.next.next; curCopy = curCopy.next; } } return copyHead; }}
转载地址:https://darkness.blog.csdn.net/article/details/105847831 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月11日 22时57分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
局部敏感哈希Locality Sensitive Hashing归总
2019-04-30
图像检索中为什么仍用BOW和LSH
2019-04-30
图˙谱˙马尔可夫过程˙聚类结构----by林达华
2019-04-30
深度学习读书笔记之AE(自动编码AutoEncoder)
2019-04-30
深度学习读书笔记之RBM
2019-04-30
深度学习word2vec笔记之基础篇
2019-04-30
android精确绘制文字位置的方法
2019-04-30
Android中UI线程与后台线程交互设计的5种方法
2019-04-30
[Android]调用字符串资源的几种方法
2019-04-30
Android更新UI的两种方法——handler与runOnUiThread()
2019-04-30
Java中new Thread的弊端及Java四种线程池的使用
2019-04-30
android线程与UI消息传递
2019-04-30
java枚举定义
2019-04-30
[翻译][Java]ExecutorService的正确关闭方法
2019-04-30
QT父子窗口事件传递与事件过滤器
2019-04-30
Qt到Cortex-A8的移植
2019-04-30
Qt4.7.3交叉编译移植
2019-04-30
luvcview摄像头程序到Cortex A8的安装移植
2019-04-30
Android开发书籍书籍介绍:
2019-04-30
QT 的信号与槽机制介绍
2019-04-30