题目描述
思路一：添加"小弟"
- 根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面。
- 原节点i的随机指针(如果有的话)，指向的是原节点j，那么新节点i的随机指针，指向的是原节点j的next
- 最后将两个链表分开，再返回新链表就可以
思路二：使用哈希表
- 首先创建一个哈希表，再遍历原链表，遍历的同时不断创建新节点
- 将原节点作为key，新节点作为value放入哈希表中
- 第二步再遍历原链表，这次我们将新链表的next和random指针给设置上
从上图中我们可以发现，原节点和新节点是一一对应的关系，所以
- map.get(原节点)，得到的就是对应的新节点
- map.get(原节点.next)，得到的就是对应的新节点.next
- map.get(原节点.random)，得到的就是对应的新节点.random
所以，我们只需要再次遍历原链表，然后设置：
新节点.next -> map.get(原节点.next)
新节点.random -> map.get(原节点.random)
这样新链表的next和random都被串联起来了
最后，我们然后map.get(head)，也就是对应的新链表的头节点，就可以解决此问题了。
方法一：对应思路一
/*
// 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) {
Node cur = head;
// 根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面
while (cur != null) {
Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = cur.next.next;
}
// 如果当前节点存在random指针的话，则复制random指针
for (Node temp = head; temp != null; temp = temp.next.next) {
if (temp.random != null) {
temp.next.random = temp.random.next;
}
}
// 将两个链表拆开
// 因为这里涉及到新建链表，所以使用dummy节点的话会比较方便
Node dummy = new Node(0);
Node p = dummy, q = head;
while (q != null) {
p.next = q.next;
q.next = q.next.next;
q = q.next;
p = p.next;
}
return dummy.next;
}
}
方法二：对应思路二
/*
// 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) {
// 创建一个哈希表，key是原节点，value是新节点
Map<Node, Node> map = new HashMap<>();
// 将原节点放入哈希表中
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 遍历原链表,设置新链表的next和random
while (cur != null) {
// cur是原节点,map.get(cur)是对应的新节点
Node newNode = map.get(cur);
if (cur.next != null) {
//map.get(p.next)是原节点下一个节点对应的新节点
newNode.next = map.get(cur.next);
}
if (cur.random != null) {
newNode.random = map.get(cur.random);
}
cur = cur.next;
}
// 返回头节点
return map.get(head);
}
}