剑指offer-25-复杂链表的复制

思路

map临时保存链表结点的映射关系，然后完成随机映射连接

代码

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
        RandomListNode p=pHead;
        RandomListNode H=new RandomListNode(0);
        RandomListNode p1=H;
        //建立next连接，并且建立原链表结点与新链表结点的映射关系
        while(p!=null){
            RandomListNode temp=new RandomListNode(p.label);
            map.put(p,temp);
            p1.next=temp;
            p=p.next;
            p1=p1.next;
        }
        //建立 random连接
        p=pHead;
        while(p!=null){
            map.get(p).random=map.get(p.random);
            p=p.next;
        }
        return H.next;
    }
}