随机链表的复制

“`” 考察点：链表

<pre><code class=""language-java"" lang=""java"">public RandomListNode copyRandomList(RandomListNode head) {

if (head == null)
return null;

RandomListNode p = head;

// copy every node and insert to list
while (p != null) {
RandomListNode copy = new RandomListNode(p.label);
copy.next = p.next;
p.next = copy;
p = copy.next;
}

// copy random pointer for each new node
p = head;
while (p != null) {
if (p.random != null)
p.next.random = p.random.next;
p = p.next.next;
}

// break list to two
p = head;
RandomListNode newHead = head.next;
while (p != null) {
RandomListNode temp = p.next;
p.next = temp.next;
if (temp.next != null)
temp.next = temp.next.next;
p = p.next;
}

return newHead;
}
</code></pre>

<pre><code> "“`