> 文档中心 > LeetCode 练习——138. 复制带随机指针的链表

LeetCode 练习——138. 复制带随机指针的链表


1.题目描述

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 作为传入参数。

示例 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]]

2.解题思路与代码

2.1 解题思路

题目中的链表节点有两个引用,一个指向下一个节点,一个指向链表中随机一个节点,要实现对这个节点的复制。首先我们还是遍历整个链表进行 next 复制,用一个 map 维护老链表的节点和新链表的节点映射。遍历完成后得到一条新的链表以及节点间的映射关系,然后再遍历一次链表对 random 引用进行复制,从 map 中根据老链表的 random 取出在新链表中的节点,最后返回新链表的头节点即可。

2.2 代码

class Solution {    public Node copyRandomList(Node head) { if (head == null){     return null; } Node newHead = new Node(head.val); Node newCurr = newHead; Node curr = head; Map<Node, Node> map = new HashMap<>(); map.put(curr, newHead); while (curr.next != null) {     curr = curr.next;     newCurr.next = new Node(curr.val);     newCurr = newCurr.next;     map.put(curr, newCurr); } curr = head; while (curr != null) {     Node random = curr.random;     map.get(curr).random = map.get(random);     curr = curr.next; } return newHead;     }}

2.3 测试结果

通过测试

LeetCode 练习——138. 复制带随机指针的链表

3.总结

  • 解题关键在于使用 map 维护新老节点映射关系