请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

分析：

方法1：哈希表

该题的难点在于 random 指针的复制，因为 random 指针可能会指向前面的节点，因此我们可以定义一个哈希表来存储复制的节点，键为旧节点，值为新节点，第一次遍历先复制链表的节点，第二次遍历复制链表的指针。

时间复杂度：O(n)
空间复杂度：O(n)

/*
// 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) {//创建哈希表HashMap<Node, Node> map = new HashMap<>();//遍历链表，复制节点，旧节点作为键，新节点作为值Node cur = head;while(cur != null){map.put(cur, new Node(cur.val));cur = cur.next;}//再次遍历链表，复制指针cur = head;while(cur != null){//获取对应复制的节点Node node = map.get(cur);//复制 next 和 random 指针node.next = map.getOrDefault(cur.next, null);node.random = map.getOrDefault(cur.random, null);//继续遍历下一个节点cur = cur.next;}//返回对应复制的节点，头节点为空时返回空return map.getOrDefault(head, null);}
}

方法2：拼装+拆分

方法1 虽然实现起来较为简单，但面试的时候还是喜欢考验在原链表上进行操作，且空间复杂度较小，因此我们可以用到拼装的方法，在每个节点之间复制一个新的节点，拿 head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 举例：

• 旧链表：    7 → 13 → 11 → 10 → 1
• 拼装链表：7 → 7* → 13 → 13* → 11 → 11* → 10 → 10* → 1 → 1*

这样就得一个拼装的链表，这样的链表满足一个特性，原链表节点（node）的 next 是指向新复制的一个节点的，因此新节点的 random 指针可以指向旧节点  random 指针的 next，即：node.next.random = node.random.next，这样就可以实现 random 的复制操作。

最后，我们再将拼装链表拆分回旧链表和新复制的链表即可，拆分可以用 node.next = node.next.next，但是注意旧链表的操作一定要在新链表之前，并且要把最后一个节点的指针指向空，因为本来指的新节点。

时间复杂度：O(n)
空间复杂度：O(1)

/*
// 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) {//空节点直接返回空if(head == null){return null;}//第一次遍历，复制并拼接新节点for(Node node = head; node != null; node = node.next.next){//复制节点Node next = new Node(node.val);//拼接next.next = node.next;node.next = next;}//第二次遍历，复制 randomfor(Node node = head; node != null; node = node.next.next){if(node.random != null){node.next.random = node.random.next;}}//定义新旧节点Node cur = head.next, pre = head, ans = cur;//第三次遍历，将缝合链表拆分成旧链表和新链表while(cur.next != null){pre.next = pre.next.next;cur.next = cur.next.next;pre = pre.next;cur = cur.next;}//令旧节点最后一个节点指向空pre.next = null;return ans;}
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof