题解 | #复杂链表的复制#

import java.util.HashMap;

public class Solution {

//过程较为繁琐，主要利用的是链表的拷贝与链表的反转，并记录好有random节点的位置与相应random节点的位置
public RandomListNode Clone(RandomListNode pHead) {
    if(pHead==null){
        return pHead;
    }
    if(pHead.next==pHead){
        RandomListNode randomListNode = new RandomListNode(pHead.label);
        randomListNode.next=randomListNode;
        if(pHead.random==null){
            return randomListNode;
        } else if(pHead.random==pHead){
            randomListNode.random=randomListNode;
            return randomListNode;
        }
    }
    RandomListNode copyRandomListNode = copyRandomListNode(pHead);
    HashMap<Integer,Integer> hashMap = new HashMap<>();
    int num =0;
    int location;
    RandomListNode cur = pHead;
    while (pHead!=null){
        if(pHead.random!=null){
            location = computeLocation(cur,pHead.random);
            hashMap.put(num,location);
        }
        num++;
        pHead=pHead.next;
    }
    int key;
    int value;
    RandomListNode keyListNode;
    RandomListNode valueListNode;
    for (Integer integer : hashMap.keySet()) {
        key = integer;
        value = hashMap.get(key);
        keyListNode = computeKeyListNode(key,copyRandomListNode);
        valueListNode = computeKeyListNode(value,copyRandomListNode);
        keyListNode.random=valueListNode;
    }
    return copyRandomListNode;
}

private RandomListNode computeKeyListNode(int location, RandomListNode copyRandomListNode) {
    int num = 0;
    while (copyRandomListNode!=null){
        if(num==location){
            return copyRandomListNode;
        }
        num++;
        copyRandomListNode = copyRandomListNode.next;
    }
    return null;
}

private int computeLocation(RandomListNode cur, RandomListNode random) {
    int num = 0;
    while (cur!=null){
        if(cur==random){
            return num;
        }
        cur=cur.next;
        num++;
    }
    return num;
}

private RandomListNode copyRandomListNode(RandomListNode pHead) {
    RandomListNode temp = null;
    RandomListNode cur;
    while (pHead!=null){
        cur = new RandomListNode(pHead.label);
        cur.next=temp;
        temp=cur;
        pHead=pHead.next;
    }
    cur = temp;
    RandomListNode res = null;
    RandomListNode temp1;
    while (cur!=null){
        temp1 = cur.next;
        cur.next=res;
        res = cur;
        cur = temp1;
    }
    return res;
}

}