题⽬描述
输⼊⼀个复杂链表（每个节点中有节点值，以及两个指针，⼀个指向下⼀个节点，另⼀个特殊指针random 指向⼀个随机节点），请对此链表进⾏深拷⻉，并返回拷⻉后的头结点。（注意，输出结果中请不要返回参数中的节点引⽤，否则判题程序会直接返回空）
思路及解答
哈希表映射
使用哈希表存储原节点和新节点的映射关系：
第一次遍历：创建所有新节点，并建立原节点到新节点的映射
第二次遍历：根据映射关系设置新节点的
next和random指针
时间复杂度：O(n)，两次遍历链表
空间复杂度：O(n)，需要存储所有节点的映射关系
节点插入拆分法
通过在原链表中插入新节点来避免使用额外空间：
节点复制插入：在每个原节点后面插入一个复制的新节点
设置random指针：新节点的random指向原节点random的下一个节点
链表拆分：将混合链表拆分为原链表和新链表
时间复杂度：O(n)，三次遍历链表
空间复杂度：O(1)，只使用固定数量的指针变量