如上图所示，这就是一个复杂链表,对于节点a他不止只有指向下一个节点b，他还有一个指向节点c的指针random

对于这个题目的解法有两种

• 用map保存旧节点和新节点之间的映射关系，如果节点已经存在那么使用存在的节点即可，如果不存在那么需要新开辟节点并存储他们之间的映射关系
• 对原链表进行完全的复制（包含数据跟节点关系），然后进行原链表跟新链表的分离

方法一

首先我们需要了解map这个Java集合的作用，其中map是一个包含有键值对的数据的集合，关系可以对于为key-value，并且可以通过查找key来查找到value。

import java.util.Map; import java.util.HashMap; public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null)return null;         RandomListNode newHead = null;//构造一个新的链表的头节点，初始化为null         RandomListNode p = pHead;//指向当前链表的头节点位置，由于头节点pHead不能随便移动，所以找一个中间变量p来指代头节点的位置         RandomListNode q = null;//这个q跟上面的p类似，都是指向头节点的中间变量，方便进行链表的节点操作         Map<RandomListNode, RandomListNode> map = new HashMap<>();//这里用新旧节点来进行一个键值对的映射 while(p != null){ if(newHead == null){                 newHead = new RandomListNode(pHead.label);                 q = newHead;                 map.put(pHead, newHead);//上面第一个if里面的判断是看新的链表的头节点如果为空的化， //直接将原链表中头节点的值赋给新链表，并且构建新旧链表的键值对映射 }else{ if(p.next!= null && map.containsKey(p.next))                     q.next = map.get(p.next);//这里是如果新链表的头节点不为空， //并且旧链表的下一个节点也不为空并且在map中可以查到该节点的键值对中的key值， //那么就可以直接将value提取出来，该值就是新链表中当前节点的下一个节点的值 else{ if(p.next!= null){                         RandomListNode temp = new RandomListNode(p.next.label);                         map.put(p.next, temp);                         q.next = temp; }//这里是如果旧链表的当前节点的下一个节点不为null，但是map中也找不到该键值对的映射， //那就只有自己进行新链表的赋值，并且从新构建键值对的映射 } if(p.random != null && map.containsKey(p.random))                     q.random = map.get(p.random); else{ if(p.random != null){                         RandomListNode temp = new RandomListNode(p.random.label);                         map.put(p.random, temp);                         q.random = temp; } }//这里的操作原理跟上面类似，但是针对的是random指针                 p = p.next;                 q = q.next; } } return newHead; } } 

这种方法的优点是可以利用map构建键值对的映射，大大的节省了时间，但是需要另外开辟新的map空间，在牛客网上提交后的结果是

方法二

1. 进行原先链表的复制，新复制出来的节点就插在原来节点的后面