描述：

?

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.

思路：

1.首先根据旧链表的值创建一个新的链表并分别将旧链表和新链表存储到listOld和listNew中。

2.然后根据旧链表中index位置的结点的random指针所指向的位置，找出旧链表指针所指向结点在listOld中的index，也即listNew中的newIndex

3.把新链表中的index位置的结点指向newIndex位置的结点，问题得解！

代码：

?

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
		if(head==null)
			return null;
		List
  
   listOld=new ArrayList
   
    ();//store the old node List
    
     listNew=new ArrayList
     
      ();//store the new node RandomListNode newHead=new RandomListNode(0); RandomListNode pListNode=head,curListNode=newHead; while(pListNode!=null)//create the new LinkList && store the old node to listOld&store the new node to listNew { listOld.add(pListNode);//store the old node RandomListNode qListNode=new RandomListNode(pListNode.label ); listNew.add(qListNode);//store the new node curListNode.next=qListNode; curListNode=qListNode; pListNode=pListNode.next; } RandomListNode qListNode=newHead.next,temp=null; pListNode=head; int indexOld=0; while(pListNode!=null)//get the index of pListNode.random ,then put the node of indexOld to che random of the current newList { temp=pListNode.random; if(temp!=null) { indexOld=listOld.indexOf(pListNode.random);//get the index of pListNode.random qListNode.random=listNew.get(indexOld);//put the node of indexOld to che random of the current newList } else { qListNode.random=null; } pListNode=pListNode.next; qListNode=qListNode.next; } return newHead.next; } }
     
    
   
  

?