力扣地址：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
这是一道中等难度的链表题，我用两种方式解答
使用额外空间
思路
- 使用Map<Node,Node> 来存储原始节点和深度拷贝的节点之间的关系
- 遍历链表，然后根据链表节点去map中获取克隆节点，此时就可以设置next节点和random节点
- 返回map.get(head)
代码如下
import java.util.HashMap;
import java.util.Map;
public class CopyRandomList {
public static void main(String[] args) {
Node node1 = new Node(11);
Node node2 = new Node(22);
Node node3 = new Node(33);
node1.next = node2;
node2.next = node3;
node1.random = node3;
node2.random = node1;
new CopyRandomList().copyRandomList(node1);
}
public Node copyRandomList(Node head){
if(head == null)
return null;
Map<Node,Node> map = new HashMap<>();
Node cur = head;
// 遍历链表，写入map
while (cur != null){
Node copyNode = new Node(cur.val);
map.put(cur,copyNode);
cur = cur.next;
}
// 从链表头开始，再次遍历
cur = head;
while (cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
}
重点在于第二个while遍历
// map.get(cur)得到的是当前节点的克隆节点，也就是设置克隆节点的下一个节点
// 克隆节点的下一个节点就是 当前节点的下一个节点的克隆节点
map.get(cur).next = map.get(cur.next);
// 设置当前克隆节点的random指针指向，所以我们需要找到当前节点的random指向的节点的克隆节点即可
map.get(cur).random = map.get(cur.random);
结果
AC
不使用额外的空间
-
遍历链表，深度拷贝当前节点，并将当前节点插入链表中
拷贝出节点1，并插入链表中
以此类推，行程一个新的链表
新的链表 -
接下来设置random节点，从新的链表中两两去除节点
设置第一个克隆节点的random节点
设置完random后的效果
random设置完毕
-
接下来需要将新链表进行拆分，将原始节点和克隆节点进行拆分
image.png 返回newHead，解题完毕
代码如下
public class CopyRandomList {
public static void main(String[] args) {
Node node1 = new Node(11);
Node node2 = new Node(22);
Node node3 = new Node(33);
node1.next = node2;
node2.next = node3;
node1.random = node3;
node2.random = node1;
new CopyRandomList().copyRandomList(node1);
}
public Node copyRandomList(Node head) {
Node cur = head;
// 将拷贝的节点插入链表中
while (cur != null){
Node next = cur.next;
Node newNode = new Node(cur.val+1);
cur.next = newNode;
newNode.next = next;
cur = next;
}
// set random
// 每次取两个节点
cur = head;
while (cur != null){
// 每次读取两个节点，也就是 cur 和 next，其中next是拷贝出来的节点
Node next = cur.next;
// 设置克隆节点的random节点，该random节点也就是cur原始节点的random的下一个节点
next.random = cur.random != null ? cur.random.next : null;
// 指针下移
cur = next.next;
}
// 链表拆分
Node oldNode = head;
Node newNode = head.next;
Node headOld = head.next;
while (oldNode != null){
oldNode.next = oldNode.next.next;
newNode.next = newNode.next != null ? newNode.next.next : null;
oldNode = oldNode.next;
newNode = newNode.next;
}
return headOld;
}
static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
}
总结
我们在解链表题的时候，尝尝会考虑使用额外的空间，这也是我们经常能想到的思路，也是比较容易实现的思路，如果在AC的时候，这个方法是没问题的，但是面对面试官，如果你给出最少使用空间的最优解，你就能脱颖而出，本文两种解法，第二种应该会更吸引面试官的眼球。如果有更好的办法，欢迎指出，互相学习。
