复杂链表的复制

这个刚开始想的是先顺着next遍历一遍链表，把所有元素都存在动态数组里。然后再遍历各个结点的random，把random都连上。
但提交后发现，next有可能无法遍历完所有的结点，比如有的结点的random连接的是并没有在next链中出现的结点。
1->2->3->4->null 5->6
如果1的random是5，那光靠next是遍历不到的。
同理，先遍历random也会丢失元素。
怎么先遍历完所有元素？纠结了我半天。然后突然想明白了：其实，不管是next，还是random，只是名字不同而已，他们只是代表了两条从pHead开始的链表。你先遍历next，那random是跳着连的；但你要先遍历random，其实random是连续的，next是跳着的。
所以，这就是个简单的路径选择问题，或者说，二叉树的左右树。只不过遍历的中途可能遍历到已经遍历过的结点，那做个标记就行了。
标记flag用int，0代表第一次来，啥没做过；1代表next已经遍历过了；2代表next，random都遍历过了，结束吧！
既然是二叉树，自然是用递归。代码如下：

import java.util.*;
public class Solution {   
    public static ArrayList<RandomListNode> alrs1;   //原始节点队列
    public static ArrayList<RandomListNode> alrs2;   //复制节点队列
    public static ArrayList<Integer> flag;           //路径选择标志

    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null){
            return pHead;
        }
        alrs1=new ArrayList<RandomListNode>();
        alrs2=new ArrayList<RandomListNode>();
        flag=new ArrayList<Integer>();

        alrs1.add(pHead);
        RandomListNode p=new RandomListNode(pHead.label);
        RandomListNode first=p;
        alrs2.add(p);
        flag.add(1);
        bianli(pHead.next,p);
        if(flag.get(0)==1){
            bianli(pHead.random,p);
        }        
        return first;
    }

    public void bianli(RandomListNode rn,RandomListNode pre){
        if(rn==null){
            return;
        }
        int loc=alrs1.indexOf(rn);
        RandomListNode buf;
        if(loc==-1){
            alrs1.add(rn);
            buf=new RandomListNode(rn.label);
            alrs2.add(buf);
            int loc2=alrs2.indexOf(pre);
            if(flag.get(loc2)==2) {
        pre.random=buf;
        }else {
        pre.next=buf;
        }
            pre=buf;
            flag.add(0);
            loc=flag.size()-1;
        }else{
            buf=alrs2.get(loc);
            pre.random=buf;
            pre=buf;
        }
        if(flag.get(loc)==0){
            flag.set(loc,1);
            bianli(rn.next,buf);
            if(flag.get(loc)==1){
                bianli(rn.random,buf);
            }            
        }else if(flag.get(loc)==1){
            flag.set(loc,2);
            bianli(rn.random,buf);
        }else{
            return;
        }
    }
}