复杂链表的复制

复杂链表的复制

• 思路比较简单，主要是利用两个ArrayList，一个用来存复杂链表的节点值，另一个用来存复杂链表的随机指针的index（也就是链表中的第几个节点）

• 处理的时候我自己是先去把一个单向链表复制完，然后再循环一次去把链表的随机指针更正上去

• 注意空指针的特殊情况就好啦

• 直接上代码

  ArrayList<Integer> array = new ArrayList<>() ;
         RandomListNode node = pHead ;
  
         if (pHead!=null){ // 存节点的label值
             while (node!=null){
                 array.add(node.label);
                 node = node.next ;
             }
  
             node = pHead ;
             ArrayList<Integer> indexs = new ArrayList<>() ;
             while (node!=null){ //存随机指针的节点index，如果没有随机指针就为null
                 if (node.random!=null) {
                     indexs.add(array.indexOf(node.random.label));
                 }else if (node.random==null){
                     indexs.add(null) ;
                 }
                 node = node.next ;
             }
  
             RandomListNode head = new RandomListNode(array.get(0)) ;
             node = head ;
  
             for (int i=1;i<array.size();i++){ // 构建出单向链表
                 node.next = new RandomListNode(array.get(i)) ;
                 node = node.next ;
             }
  
             node = head ;
  
             for (int i=0;i<indexs.size();i++){ //给新构建的单向链表更正随机指针
                 if (indexs.get(i)!=null) {
  
                     RandomListNode temp = head ;
                     for (int j=0;j<indexs.get(i);j++){ //用于获取随机指针的地址
                         temp = temp.next ;
                     }
  
                     node.random = temp;
                 }
                 node = node.next ;
  
             }
  
             return head ;
         }else { //空指针就特殊处理掉
             return null ;
         }