字典存储随机节点法
- 第一次循环复制新链,并且建立新节点和旧节点的映射存入map中
- 第二次循环利用map给新链重定向随机节点指向
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> map = new HashMap();
RandomListNode head = new RandomListNode(-1), node = head, pre;
// 克隆链表
while(pHead != null) {
pre = node;
// 深拷贝节点
node = new RandomListNode(pHead.label);
node.random = pHead.random;
// 连接
pre.next = node;
// 存入映射
map.put(pHead, node);
pHead = pHead.next;
}
// 克隆随机节点
node = head.next;
while(node != null) {
node.random = map.get(node.random);
node = node.next;
}
return head.next;
}
}
后置节点法
- 第一个循环创建复制节点,并放置原节点之后
- 第二个循环给每一个复制节点的随机指针赋值
- 第三个循环独立出复制节点,并还原链
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> map = new HashMap();
RandomListNode head = new RandomListNode(-1), node = head, pre;
head.next = pHead;
// 将克隆节点放到原节点后
while(pHead != null) {
node = new RandomListNode(pHead.label);
node.random = pHead.random;
node.next = pHead.next;
pHead.next = node;
pHead = node.next;
}
// 给克隆节点的随机节点赋值
node = head.next;
while(node != null) {
node = node.next;
node.random = node.random == null ? null : node.random.next;
node = node.next;
}
// 独立出克隆节点
node = head;
pHead = head.next;
while(node.next != null) {
pre = node;
node = node.next.next;
pHead.next = node.next;
pre.next = node;
pHead = pHead.next;
}
return head.next;
}
}