Copy List with Random Pointer, Leetcode 解题笔记

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.

思路与Clone Graph完全一样,利用hashmap来映射新旧node。

 * 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) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = head;
        RandomListNode newhead = new RandomListNode(0);
        RandomListNode pre = newhead;
        RandomListNode n;
        while(cur != null){
            n = new RandomListNode(0);
            n.label = cur.label;
   = n;
            pre = n;
            map.put(cur, n);
            cur =;
        newhead =;
        cur = head;
        n = newhead;
        while(cur != null){
            n.random = map.get(cur.random);
            cur =;
            n =;
        return newhead;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s