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 /** 2  * Definition for singly-linked list with a random pointer. 3  * class RandomListNode { 4  *     int label; 5  *     RandomListNode next, random; 6  *     RandomListNode(int x) { this.label = x; } 7  * }; 8  */ 9 public class Solution {10     public RandomListNode copyRandomList(RandomListNode head) {11         if(head==null)12             return null;13         RandomListNode p=head; //拷贝当前节点，并将其插入到被拷贝节点的后方14         while(p!=null){15             RandomListNode temp=new RandomListNode(p.label);16             temp.next=p.next;17             p.next=temp;18             p=temp.next;19         }20         p=head; //将拷贝节点的随机指针指向应有位置21         while(p!=null){22             if(p.random!=null){23                 p.next.random=p.random.next;24             }25             p=p.next.next;26         }27         RandomListNode newhead=head.next;28         p=head; //将拷贝链表与原链表分离29         while(p!=null){30             RandomListNode temp=p.next;31             p.next=temp.next;32             if(temp.next!=null)33                 temp.next=temp.next.next;34             p=p.next;35         }36         return newhead;37     }38 }

最后分离也可这样写：

1 while(p != null && p.next != null){2     RandomListNode temp = p.next;3     p.next = temp.next;4     p = temp;5 }

解法2：

可以用hashmap的方式

1 public RandomListNode copyRandomList(RandomListNode head) { 2     if (head == null) 3         return null; 4     HashMap
     
       map = new HashMap
      
       (); 5     RandomListNode newHead = new RandomListNode(head.label); 6   7     RandomListNode p = head; 8     RandomListNode q = newHead; 9     map.put(head, newHead);10  11     p = p.next;12     while (p != null) {13         RandomListNode temp = new RandomListNode(p.label);14         map.put(p, temp);15         q.next = temp;16         q = temp;17         p = p.next;18     }19  20     p = head;21     q = newHead;22     while (p != null) {23         if (p.random != null)24             q.random = map.get(p.random);25         else26             q.random = null;27  28         p = p.next;29         q = q.next;30     }31  32     return newHead;33 }