【解题报告】lintcode105复制带随机指针的链表

题意

给出一个链表，每个节点带一个随机指针，复制它

解法

由于有随机指针，如果顺序复制的话，有可能随机指针指向的节点还没有存在，会有问题 解法，首先复制每个节点，插入到其后 此时所有节点都初始化了，再初始化随机指针，把新节点和原来的节点分开

代码

public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        RandomListNode copyNode,node,node1;
        if (head == null)
            return null;
        if (head.next == null){
          copyNode =  new RandomListNode(head.label);
            copyNode.random = head.random;
            return  copyNode;
        }
        node = head;
       //复制节点
        while (node != null){
            node1 = node.next;
            copyNode = new RandomListNode(node.label);
            copyNode.next =  node.next;
            node.next = copyNode;
            node = node1;
        }
        node = head;
      //初始化随机指针
        while (node!=null){
          if (node.random!=null)
            node.next.random = node.random.next;
            node = node.next.next;
        }
        node = head.next;
      //新节点指向新节点，移除与旧节点的关系
        while (node.next != null){
            node.next = node.next.next;
            node = node.next;
        }
        return head.next;
    }
}