138. 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.

/**
 * 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 {
    // Solution 2:
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return head;
        }
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode newNode = dummy;
        while (cur != null) {
            newNode.next = new RandomListNode(cur.label);
            newNode = newNode.next;
            map.put(cur, newNode);
            cur = cur.next;
        }
        cur = head;
        newNode = dummy.next;
        while (cur != null) {
            newNode.random = map.get(cur.random);
            newNode = newNode.next;
            cur = cur.next;
        }
        return dummy.next;
    }
    /**
     * Solution 1: Dup first, copy, break.
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        // Dup the original list, with dup node after each original one.
        RandomListNode cur = head;
        while (cur != null) {
            // Pay attention not to use head.label, should use cur.label.
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = cur.next.next;
        }
        cur = head;
        while (cur != null) {
            // Need to take care of cur.random == null, or ther will be NullPointerException.
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        RandomListNode newHead = head.next;
        while (cur != null) {
            RandomListNode curNew = cur.next;
            cur.next = curNew.next;
            // Have to check curNew.next != null, or there will be NullPointerException.
            if (curNew.next != null) {
                curNew.next = curNew.next.next;
            }
            // cur.next has already been set to point to the new position. Do not use cur = cur.next.next.
            cur = cur.next;
        }
        return newHead;
    }
    */
}

//////////////////////////////////////
//HashMap version
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode pre = dummy, newNode;
        while (head != null) {
            if (map.containsKey(head)) {
                newNode = map.get(head);
            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            }
            pre.next = newNode;

            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    newNode.random = map.get(head.random);
                } else {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                }
            }

            pre = newNode;
            head = head.next;
        }

        return dummy.next;
    }
}

/*第一遍扫的时候巧妙运用next指针, 开始数组是1->2->3->4  。 然后扫描过程中 先建立copy节点 1->1`->2->2`->3->3`->4->4`, 然后第二遍copy的时候去建立边的copy, 拆分节点, 一边扫描一边拆成两个链表,这里用到两个dummy node。第一个链表变回  1->2->3 , 然后第二变成 1`->2`->3`  */
//No HashMap version
public class Solution {
    private void copyNext(RandomListNode head) {
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random;
            newNode.next = head.next;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.next.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            head = head.next;
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
        }
        return newHead;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }
}
///////////////////////////////////////
// Recursion:
Map<RandomListNode, RandomListNode> map = new HashMap<>();  
public RandomListNode copyRandomList(RandomListNode head) {  
    if(head == null) return null;  
    RandomListNode copy = map.get(head);  
    if(copy == null) {  
        copy = new RandomListNode(head.label);  
        map.put(head, copy);  
        copy.next = copyRandomList(head.next);  
        copy.random = copyRandomList(head.random);  
    }  
    return copy;  
}

Reference:
http://www.cnblogs.com/springfor/p/3864457.html
http://yuanhsh.iteye.com/blog/2185974

如果要copy一个带有random pointer的list,主要的问题就是有可能这个random指向的位置还没有被copy到,所以解决方法都是多次扫描list。

第一种方法,就是使用HashMap来坐,HashMap的key存原始pointer,value存新的pointer。

第一遍,先不copy random的值,只copy数值建立好新的链表。并把新旧pointer存在HashMap中。

第二遍,遍历旧表,复制random的值,因为第一遍已经把链表复制好了并且也存在HashMap里了,所以只需从HashMap中,把当前旧的node.random作为key值,得到新的value的值,并把其赋给新node.random就好。

第二种方法不使用HashMap来做,使空间复杂度降为O(1),不过需要3次遍历list,时间复杂度为O(3n)=O(n)。

第一遍,对每个node进行复制,并插入其原始node的后面,新旧交替,变成重复链表。如:原始:1->2->3->null,复制后:1->1->2->2->3->3->null

第二遍,遍历每个旧node,把旧node的random的复制给新node的random,因为链表已经是新旧交替的。所以复制方法为:

node.next.random = node.random.next

前面是说旧node的next的random,就是新node的random,后面是旧node的random的next,正好是新node,是从旧random复制来的。

第三遍,则是把新旧两个表拆开,返回新的表即可。

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