递归和哈希表
时间&空间复杂度 O（n）
复杂链表的特点是每个节点除了有一个指向下一个节点的指针外，还有一个随机指针可能指向链表中的任意节点或null。通过递归和哈希表的方式，能够确保每个节点只被复制一次，并且正确地复制了next和random指针。
/*
// 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 {
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (!map.containsKey(head)) {
Node node = new Node(head.val);
map.put(head, node);
node.next = copyRandomList(head.next);
node.random = copyRandomList(head.random);
}
return map.get(head);
}
}
迭代 + 节点拆分
时间复杂度O(n), 空间复杂度O(1)
在不使用额外哈希表的情况下复制带有随机指针的链表。这种方法通过在原链表中插入拷贝节点来实现，具体步骤如下：
插入拷贝节点：
遍历原链表，对于每一个节点，创建一个新节点，其值与原节点相同，并将新节点插入到原节点之后。例如，对于链表 A→B→C，插入拷贝节点后变为 A→A'→B→B'→C→C'。
设置拷贝节点的随机指针：
再次遍历链表，对于每一个原节点 S，其拷贝节点 S' 的随机指针应当指向 S 的随机指针指向的节点 T 的拷贝节点 T'。即，如果 S.random 指向 T，那么 S'.random 应当指向 T'。
需要注意原节点的随机指针可能为空，此时拷贝节点的随机指针也应为空。
拆分链表：
最后，遍历链表，将原节点和拷贝节点分开，形成两个独立的链表。原链表恢复原状，新链表即为拷贝链表。
需要注意最后一个拷贝节点的后继节点为空。
假设有一个链表：A → B → C，其中每个节点除了有next指针外，还可能有指向链表中任意节点或null的random指针。下面是使用不需要额外哈希表的方法复制这个链表的可视化过程：
初始链表
A → B → C
步骤1：插入拷贝节点
在每个原节点后面插入一个拷贝节点，此时不处理random指针。
A → A' → B → B' → C → C'
步骤2：设置拷贝节点的随机指针
对于每个原节点，比如A，如果A.random指向C，则设置A'.random指向C'。这一步骤完成后，所有拷贝节点的random指针都会正确指向对应的拷贝节点。
A → A' → B → B' → C → C'
| | | | | |
v v v v v v
C C' A A' B B'
步骤3：拆分链表
将原节点和拷贝节点分开，形成两个独立的链表。原链表恢复为A → B → C，新链表为A' → B' → C'。
原链表：
A → B → C
拷贝链表：
A' → B' → C'
在这个过程中，原链表完全恢复，而新链表是原链表的深拷贝，包括正确复制的random指针。这种方法避免了使用额外的哈希表来存储节点之间的映射关系，通过巧妙地在原链表中插入拷贝节点并最后将它们分离出来，实现了空间复杂度为O(1)的深拷贝。
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Step 1: Insert copy nodes
Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
// Step 2: Set random pointers for copy nodes
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate the original and copy lists
Node dummy = new Node(0);
Node copyPrev = dummy;
curr = head;
while (curr != null) {
copyPrev.next = curr.next;
copyPrev = copyPrev.next;
curr.next = curr.next.next;
curr = curr.next;
}
return dummy.next;
}
}