剑指offer-26：复杂链表的复制

题目：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

思路

1. 复制过程分为两步：
   （1）复制节点，并利用hashmap记录节点N与N’的映射关系；
   （2）再次遍历，处理节点random关系；

         import java.util.HashMap;
         /*
         public class RandomListNode {
           int label;
           RandomListNode next = null;
           RandomListNode random = null;
   
           RandomListNode(int label) {
               this.label = label;
           }
         }
         */
         public class Solution {
           public RandomListNode Clone(RandomListNode pHead) {
               if (pHead == null)
                   return null;
   
               // 新节点到老节点的映射
               HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
               RandomListNode root = new RandomListNode(pHead.label);
   
               // 记录next关系
               RandomListNode temp1 = pHead;
               RandomListNode temp2 = root;
               map.put(temp1, temp2);
               while (temp1.next != null) {
                   temp1 = temp1.next;
                   temp2.next = new RandomListNode(temp1.label);
                   temp2 = temp2.next;
                   map.put(temp1, temp2);
               }
   
               // 记录random关系
               temp1 = pHead;
               temp2 = root;
               while (temp1 != null) {
                   temp2.random = map.get(temp1.random);
                   temp1 = temp1.next;
                   temp2 = temp2.next;
               }
               return root;
           }
       }
   

2. 时间优化：两步合并，节省一次遍历开销；
   复制节点N时创建next节点和random节点，并记录到hashmap中，接下来查询hashmap决定是否创建next节点；

   public class Solution {
   public RandomListNode Clone(RandomListNode pHead) {
       if (pHead == null)
           return null;
   
       // 新节点到老节点的映射
       HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
       RandomListNode root = new RandomListNode(pHead.label);
       RandomListNode temp1 = pHead;
       RandomListNode temp2 = root;
       map.put(temp1, temp2);
       while (temp1.next != null) {
           // 复制next
           RandomListNode next_new = map.get(temp1.next);
           if (next_new == null) {
               next_new = new RandomListNode(temp1.next.label);
               map.put(temp1.next, next_new);
           }
           temp2.next = next_new;
   
           // 复制random
           if (temp1.random != null) {
               RandomListNode random_new = map.get(temp1.random);
               if (random_new == null) {
                   random_new = new RandomListNode(temp1.random.label);
                   map.put(temp1.random, random_new);
               }
               temp2.random = random_new;
           }
   
           temp1 = temp1.next;
           temp2 = temp2.next;
       }
       return root;
   }
   }