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;
            pre.next = n;
            pre = n;
            map.put(cur, n);
            cur = cur.next;
        }
        newhead = newhead.next;
        
        cur = head;
        n = newhead;
        while(cur != null){
            n.random = map.get(cur.random);
            cur = cur.next;
            n = n.next;
        }
        return newhead;
        
    }
}
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s