【剑指OFFER】面试题35. 复杂链表的复制
发布日期:2021-06-29 19:46:23
浏览次数:2
分类:技术文章
本文共 1801 字,大约阅读时间需要 6 分钟。
题目:请实现 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 <= 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/105847802 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月22日 04时20分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
详解YUV420数据格式
2019-04-30
Gstreamer学习笔记(2):GstElement定义、连接
2019-04-30
GStreamer建议的学习步骤和网页链接汇总
2019-04-30
Ubuntu14.04编译安装GStreamer
2019-04-30
GStreamer(一)
2019-04-30
GStreamer(二)
2019-04-30
Gstreamer学习笔记(1):GStreamer Debugging
2019-04-30
bitbake常用命令
2019-04-30
Git学习(一):git 生成 patch的命令
2019-04-30
Gstreamer学习笔记(8):Gobject类对象
2019-04-30
Gstreamer学习笔记(7):plugin注册流程分析(超详细)
2019-04-30
Gstreamer学习笔记(6):如何创建gstreamer插件?
2019-04-30
AVI封装格式解析
2019-04-30
rmvb 文件格式解析
2019-04-30
C语言:setjmp和longjmp函数使用详解
2019-04-30
FFmpeg常用基本命令
2019-04-30
MPG(MPEG2 Program Stream)格式解析
2019-04-30
Gstreamer学习笔记(4):pad定义、连接、流动
2019-04-30
Gstreamer 学习笔记(3):GstElement状态
2019-04-30