外贸门户网站,中国科技成就,网站访问量突然增加,2017做那些网站致富目录 题目描述#xff1a;138. 复制带随机指针的链表#xff08;中等#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;138. 复制带随机指针的链表#xff08;中等#xff09;
给你一个长度为 n 的链表#xff0c;每个节点包含一个额外增加的随机指针 random 138. 复制带随机指针的链表中等题目接口解题思路代码 PS: 题目描述138. 复制带随机指针的链表中等
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
LeetCode做题链接LeetCode-复制带随机指针的链表
示例 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]]提示
0 n 1000
-104 Node.val 104
Node.random 为 null 或指向链表中的节点。题目接口
/*
// 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) {}
}解题思路
参考题解图解 138. 复制带随机指针的链表 主要思路
1.根据遍历到的原节点创建对应的新节点每个新创建的节点是在原节点后面2.新节点的随机指针就是原节点的随机指针的next重点3.将两个链表分开返回新链表
代码
/*
// 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) {if (head null) {return null;}Node p head;//第一步在每个原节点后面创建一个新节点//1-1-2-2-3-3while (p ! null) {Node newNode new Node(p.val);newNode.next p.next;p.next newNode;// p 指向原链表的的下一个结点然后继续插入p newNode.next;}p head;//第二步设置新节点的随机节点while (p ! null) {if (p.random ! null) {// 新节点的随机指针就是原节点的随机指针的nextp.next.random p.random.next;}// 每次都跳两次p p.next.next;}// 定义一个新的链表头结点这个结点的next才是我们需要返回的新链表Node dummy new Node(-1);p head;Node cur dummy;//第三步将两个链表分离while (p ! null) {cur.next p.next;cur cur.next;p.next cur.next;p p.next;}return dummy.next;}
}成功
PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
