一. 题目描述
题目链接：复制带随机指针的链表
题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
示例：
自己举一个例子：
二. 方法一解析及参考代码
我们采用链表相关概念来做，具体的做法分为三大步骤：
1. 复制链表节点进行链接，复制链接完后长这样：
2. 给复制的新节点赋随机指针域，赋完长这样：
3. 将复制的新链表从原链表中断开，断开为这样：
参考代码：
class Solution { public Node copyRandomList(Node head) { //判空操作，如果链表为空直接返回 if(head == null){ return head; } //复制链接 Node cur = head; while(cur != null){ Node newNode = new Node(cur.val);//以原链表的值new新节点 newNode.next = cur.next; cur.next = newNode; cur = newNode.next; } //给复制的节点赋随机值 cur = head; Node newNode = cur.next; while(cur != null){ if(cur.random != null){ newNode.random = cur.random.next; } cur = newNode.next; if(cur != null){ newNode = cur.next; } } //将复制的链表从原链表当中断开 cur = head; Node newHead = cur.next;//新链表头节点 Node newCur = newHead;//新链表节点的引用 while(cur != null){ cur.next = newCur.next; cur = newCur.next; if(cur != null){ newCur.next = cur.next; newCur = cur.next; } } return newHead; } }
三. 方法二解析及参考代码
我们借助hashmap这一数据结构来做，具体做法分为三大步骤：
1. 遍历原链表，将原链表的节点作为K，新复制的节点作为V，将K与对应的V存入hashmap中，存入之后为这样：
2. 将hashmap中V的节点依次链接起来，链接后为这样：
3. 给hashmap中V的节点依次赋随机指针域，完成后为这样：
参考代码：
class Solution { public Node copyRandomList(Node head) { Map<Node,Node> m = new HashMap<>(); Node cur = head; //hashmap中存放的K-V为：原链表的节点-新复制的节点 while(cur != null){ m.put(cur,new Node(cur.val)); cur = cur.next; } cur = head; while(cur != null){ m.get(cur).next = m.get(cur.next);//将V中的节点链接起来 m.get(cur).random = m.get(cur.random);//给V中的节点赋随机指针域 cur = cur.next; } return m.get(head); } }
