Copy List with Random Pointer

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.

这道题主要的问题是怎么样处理random pointer,不能直接copy pointer,我们要的是deep copy,而我们没办法将旧的node和新copy的node对应起来。所以新node里的randompointer就没法copy。办法就是建一个Hashmap,将旧的node map到新的node上(还有一种办法是将旧的node的next指针指向新的node,这样也可以,但是要copy一份旧的list,用的space也是一样多O(n))。

code如下,先将所有的node通过next pointer copy一遍,将旧的node和新的node放进hashmap里,然后再走一遍,random pointer指向的node通过hashmap找到对应的copy的值,然后copy中的random指向他就可以了

/**
 * 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>(); // store mapping of the original list and copy list
        if (head == null)
            return null;
        RandomListNode p = head;
        RandomListNode copy = new RandomListNode(head.label);
        p = p.next;
        RandomListNode n = copy;
        map.put(head, copy);
        while(p != null)
        {
            n.next = new RandomListNode(p.label);
            map.put(p, n.next);
            n = n.next;
            p = p.next;
        }
        n.next = null; //last pointer for the copy list.
        //random pointer
        p = head;
        n = copy;
        while(p != null)
        {
            n.random = map.get(p.random);
            p = p.next;
            n = n.next;
        }
        return copy;
    }
}

上面这个code需要一个O(n)的额外位置来存放hashmap,如果用constant的space用以下办法即可

scan原list,每碰到一个node就copy一个node,并将这个node插入到原node之后,例如node,1,2,3,就变成1,copy1, 2 copy2, 3…
然后再遍历这个新的list,copylist中的random指针按照原list设好,最后再将两个list分开即可。

/**
 * 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;
        RandomListNode n = head;
        while(n != null)
        {
            RandomListNode t = new RandomListNode(n.label);
            t.next = n.next;
            n.next = t;
            n=t.next;
        }
        
        n = head;
        while(n != null)
        {
            n.next.random = (n.random == null)? null : n.random.next;
            n = n.next.next;
        }
        
        //split
        RandomListNode copy = head.next;
        n = head;
        RandomListNode p = copy;
        while(n != null)
        {
            n.next = p.next;
            n = p.next;
            if (n == null)
                break;
            p.next = n.next;
            p = p.next;
        }
        return copy;
    }
}

第二次代码,如果不要求原来输入不变,也可以通过将原来的数组的next指针指向对应的新的copy,也是constant space并且更容易实现.hashmap在这里可以用是因为key就是原来list中Node的地址,如果不是这种情况要考虑overload equals和hashCode函数


/**
 * 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;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode curr = head;
        RandomListNode helper = new RandomListNode(-1);
        RandomListNode result = helper;
        while(curr != null) {
            result.next = new RandomListNode(curr.label);
            map.put(curr, result.next);
            result.next.random = curr.random;
            result = result.next;
            curr = curr.next;
        }
        result = helper.next;
        while(result != null) {
            result.random = map.get(result.random);
            result = result.next;
        }
        return helper.next;
    }
}

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