Amazon-Copy List with Random Poi

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution:

public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        RandomListNode iter=head;
        while(iter!=null){
            RandomListNode copy=new RandomListNode(iter.label);
            copy.next=iter.next;
            iter.next=copy;
            
            iter=iter.next.next;
        }
        iter=head;
        while(iter!=null){
            if(iter.random!=null){
                iter.next.random=iter.random.next;
            }else{
                iter.next.random=null;
            }
            iter=iter.next.next;
        }
        
        RandomListNode dump=new RandomListNode(0);
        dump.next=head;
        iter=dump;
        while(head!=null){
            iter.next=head.next;
            head.next=iter.next.next;
            iter=iter.next;
            head=head.next;
        }
        iter.next=null;
        RandomListNode res=dump.next;
        dump.next=null;
        dump=null;
        return res;
        
    }

时间复杂度：O(n)
空间复杂度：O(n)

第一步复制每个节点，复制节点连在原节点后。第二步修改复制节点random指针。第三步拆分链表。题目里要求不能改动原链表，所以只能拆分并输出。虚拟头节点最好断开连接。我试过边拆分边修改random指针，其实这里有一个错误，就是并不知道random是不是指未拆分的节点，所以不能合并在一起遍历。
也可以用哈希表方式<RandomListNode,RandomListNode>，key是节点，value是random指针的值，可以递归，递归开始put节点，然后根据哈希表修改random指针，递归终止于null，空间复杂度是O(n)。