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.

思路: 深度拷贝一个含有随机值得链表, 可以用一个map来记录原始点跟拷贝点的映射关系; 我们可以用一个dummy节点来链接拷贝的节点值,pre节点为被拷贝节点的前一个节点,把它指向dummy节点。 然后我们还需要一个被拷贝节点copyNode来存放拷贝值。 先拷贝head节点,然后查看head.random节点是否为空,不空的话就拷贝其random节点。拷贝的时候先看map重是否存了该节点,如果存了copy节点就可以直接拿到,否则创建个新的节点并把原节点-> copy节点存入map中。 拷贝完了,讲pre节点跟head节点往后移动,最后直到head为null,即拷贝结束。

/**
 * 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 dummy = new RandomListNode(0);
        RandomListNode pre = dummy, copyNode;
        while(head != null) {
            // copy head node
            if(map.containsKey(head)) {
                copyNode = map.get(head);
            } else {
                copyNode = new RandomListNode(head.label);
                map.put(head, copyNode);
            }
            pre.next = copyNode;
            // copy random node
            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    copyNode.random = map.get(head.random);
                } else {
                    copyNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, copyNode.random);
                }
            }

            pre = copyNode;
            head = head.next;
        }
        return dummy.next;
    }
}

空间复杂度O(1)做法, 重新构造链表, 如下图所示.
1. 复制原来节点,并将拷贝节点连接到原节点后面。
2. 更新拷贝节点的random节点, 可以用head.next.random = head.random.next实现。
3. 将原来链表与拷贝链表断开。
b4f7858a-db87-3ae3-9c8e-bd413f05ad2b.pngb4f7858a-db87-3ae3-9c8e-bd413f05ad2b

/**
 * 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 h = head;
        while(h != null) {
            RandomListNode copy = new RandomListNode(h.label);
            RandomListNode next = h.next;
            h.next = copy;
            copy.next = next;
            // move h to the right
            h = next;
        }
        h = head;
        // copy random node
        while(h != null) {
            if (h.random != null) {
                h.next.random = h.random.next;
            }
            h = h.next.next;
        }
        // reset head and copy head
        h = head;
        RandomListNode newHead = head.next;
        // split original and copy 
        while(h != null) {
            RandomListNode copy = h.next;
            h.next= copy.next;
            h = h.next;
            copy.next = h == null ? null: h.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