GuilinDev

Lc0138

05 August 2008

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.

题意和分析

这道题还是链表的操作，给一个链表，这个链表在正常链表的基础上还带有一个random pointer，这个random pointer可以指向别的结点，也可以指向null，然后问题是如何deep copy这个链表。

假设原始链表如下，细线表示next指针，粗线表示random指针，没有画出的指针均指向NULL：

算法1：先按照复制一个正常链表的方式复制，复制的时候把复制的结点做一个HashMap，以旧结点为key，新节点为value。这么做的目的是为了第二遍扫描的时候按照这个哈希表把结点的随机指针接上。下图蓝色为原始链表节点，红色为新链表节点：

然后在上图的基础上进行如下两步

1、构建新链表的random指针：比如

new1.random = new1.random.random.next,

new2.random = NULL,

new3.random = NULL,

new4.random = new4.random.random.next

2、恢复原始链表：根据最开始保存的原始链表next指针映射关系恢复原始链表

该算法总共要进行两次扫描，所以时间复杂度是O(2*n)=O(n)，空间复杂度为需要哈希表来做映射，所以也是O(N)。

算法2：该算法更为巧妙，不用保存原始链表的映射关系，构建新节点时，指针做如下变化，即把新节点插入到相应的旧节点后面：

同理分两步

1、构建新节点random指针：new1->random = old1->random->next, new2-random = NULL, new3-random = NULL, new4->random = old4->random->next

2、恢复原始链表以及构建新链表：例如old1->next = old1->next->next, new1->next = new1->next->next

该算法时间复杂度O(N)，空间复杂度O(1)。

代码

HashMap的做法，需要一个哈希表的原因是当我们访问一个结点时可能它的随机指针指向的结点还没有访问过，结点还没有创建，所以需要线性的额外空间，时间和空间都是O(n)。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>(); // k-v分别是节点本身和该节点的随机指针
        Node node = head;
        while (node != null) { // 用散列表保存节点和其随机指针
            map.put(node, new Node(node.val)); // 这里需要new对象，才是deep copy
            node = node.next;
        }
        node = head; // 临时指针指回头部，准备开始copy
        while (node != null) {
            map.get(node).next = map.get(node.next); // 当前节点的next指针通过hashmap的key来寻找，O(1)
            map.get(node).random = map.get(node.random); // 当前节点的random通过hashmap的key来寻找，O(1)
            node = node.next;
        }
        return map.get(head); //返回存储在hashmap的头节点，这时候已经是hashmap + linkedlist的结构了
    }
}

in-place的做法，想避免使用额外空间，我们只能通过利用链表原来的数据结构来存储结点。基本思路是这样的，对链表进行三次扫描，第一次扫描对每个结点进行复制，然后把复制出来的新节点接在原结点的next，也就是让链表变成一个重复链表，就是新旧更替；第二次扫描中我们把旧结点的random指针赋给新节点的random指针，因为新结点都跟在旧结点的下一个，所以赋值比较简单，就是node.next.random = node.random.next，其中node.next就是新结点，因为第一次扫描就是把新结点接在旧结点后面。现在把结点的随机指针都接好了，最后一次扫描把链表拆成两个，第一个还原原链表，而第二个就是我们要求的复制链表。因为现在链表是旧新更替，只要把每隔两个结点分别相连，对链表进行分割即可。这个方法总共进行三次线性扫描，所以时间复杂度是O(n)。而这里并不需要额外空间，所以空间复杂度是O(1)。比起上面的方法，这里多做一次线性扫描，但是不需要额外空间，还是比较值的。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Node node = head; // 用来遍历的索引
        Node copy = null; // 用来复制当前节点，作为不用额外数据结构而用临时的变量
        Node next = null; // 用来记录当前节点的下一个节点以免丢失
        
        // 第一次遍历，复制节点本身，并附着到该节点的后面，使原来的链表变为二倍size
        while (node != null) {
            next = node.next;
            
            copy = new Node(node.val); // deep copy
            node.next = copy;
            copy.next = next;
            
            node = next;
        }
        
        // 第二次遍历， 把random指针assign到上一步附着的各个copy节点上
        node = head;
        while (node != null) {
            // 当前节点（旧结点A1）的下一个节点（新节点A2）的random指针（旧节点B1），等于当前节点（旧节点A1）的random指针指向的节点（旧节点B1）的next（新节点B2）
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next; //跳两步，跨过后面自己的复制节点
        }
        
        // 第三次遍历，把双倍size的链表分撤，只剩下第一步复制的节点
        Node dummy = new Node(-1);
        copy = dummy;
        Node newNode = dummy;
        node = head;
        while (node != null) {
            next = node.next.next; // 先记住“双子星”的next
            
            copy = node.next;
            newNode.next = copy;
            newNode = copy; // 新的节点指针移动“一步”，其实是两步
            
            // 还原原先的链表 (如果不需还原则可以省区newNode这个变量)
            node.next = next;
            node = next; // 旧的节点指针移动“一步”，其实是两步
        }
        return dummy.next;
    }
}

This site is open source. Improve this page.