leetcode: 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.

原问题链接：https://oj.leetcode.com/problems/copy-list-with-random-pointer/

 

问题分析

     这个问题粗看起来确实不好解决，因为这不是一个单纯的linked list的拷贝，它里面还包含了一些随机指向某些节点的指针。对于链表里指向每个元素后面的元素都还好说，只要沿着原来的地方一个个的拷贝过去就可以。可是这些随机指向的可能就跳到不知道哪里去了。在原来的说明里已经给出了linked list里面每个节点的定义：

class RandomListNode {
     int label;
     RandomListNode next, random;
     RandomListNode(int x) { this.label = x; }
}

 

初步探讨

   我们先假定有一个如下图的随机链表：

     如果我们不考虑随机指向的链接的话，我们每次访问原链表中一个元素时，可以直接建立一个对应的拷贝。当原来的元素要指向下一个元素时，我们再建一个下一个元素的拷贝，然后将原来的元素指向新建的下一个元素。这个过程类似于一个递归的过程，当然，通过这个过程我们可以建立一个如下图这样的拷贝效果:

    这是在仅仅考虑指向后续元素引用的情况下。如果一旦我们创建好这个之后，随机引用的指针就反而不好处理了。假如在原来的链表中，有第一个元素的随机指针指向第三个元素，我在拷贝的链表里怎么知道呢？因为一旦拷贝出来之后，在新拷贝的链表里是没法知道怎么对应的。难道我们还要去专门建立一个新建元素和原来链表元素的一一映射吗？而且就算我们去建立这么一个映射，难道用Map就一定能解决？如果原来的链表里有值相同的元素呢？会不会没法区分？看来就这么直接复制过来的办法不可行。

 

换一种思路

    其实，在前面我们复制每个链表节点的时候，我们只要从头开始，每次必然可以构造出该节点对应的拷贝。如果我们每次新建的链表节点不急着放到外面来拼装成一个链表，而是先放到每个对应链表节点的后面呢？比如下图的这样：

 

     我们用更深蓝色的节点表示拷贝节点，这样它们就形成了一个原节点和拷贝节点相间的这么一个结构。现在，我们再来考虑随机指针。因为在原来节点中，随机指针指向了某个节点，在这个增加了拷贝节点之后的链表里，其实原来的指针是没有任何变化的。但是因为我们新加入的拷贝节点都是在对应节点的后面一个。这不就正好方便我们来处理随机指针了吗？

    因为原来对于某个节点它随机指针指向了一个节点，而我拷贝节点是原节点的后面一个。那么对应拷贝节点的随机指针不就是对应原来节点所指向的随机指针后面的那个吗？我们把随机指针加上来考虑的话，则我们新拷贝的节点和原来节点的关系如下图：

     按照这个关系，我们处理随机指针就可以按照如下的方式：

    1. 每次碰到一个原有节点的时候，假定原节点为a, 先记录一下它后面的那个拷贝节点，假设拷贝节点为b。

    2. 将a节点所指向的随机节点后面那个元素，即a.random.next设置为拷贝节点的随机指针目的。也就是b.random = a.random.next。

    在完成了上述步骤之后，我们就需要将上图中拷贝的元素部分再剥离出来。因为随机指针在前一步都已经设置好了，它们不会受到影响。所以这里的剥离也就很简单了，设置一前一后两个指针，每个都跳一个指向后面的元素就可以了。

 

综合

    综合上面的讨论，这个问题的解决步骤如下：

1. 遍历原有链表，在每个原来的节点后面增加一个拷贝节点。

2. 根据原节点的随机指针设置拷贝节点的随机指针。

3. 剥离出所有拷贝节点。

    按照这个思路，第一步的代码实现如下：

RandomListNode copy = head;
        while(copy != null) {
            RandomListNode node = new RandomListNode(copy.label);
            node.next = copy.next;
            copy.next = node;
            copy = node.next;
        }

     因为我们需要在每个节点后面创建一个拷贝节点，同时不希望修改原有的初始节点，所以开始的时候创建了一个head节点的拷贝copy。每次将新建的node插入到copy节点后面。在设置完了第一步之后我们需要再从拷贝节点的第一个开始去设置随机指针。它的实现如下：

copy = head;
        while(copy != null && copy.next != null) {
            if(copy.random != null)
                copy.next.random = copy.random.next;
            copy = copy.next.next;
        }

     因为每次要跳过它后面的节点，所以这里copy = copy.next.next;

    剩下的就是第三步，剥离拷贝节点：

   

        copy = head;
        RandomListNode cur  = head.next;
        RandomListNode tmp = cur;
        while(copy != null && tmp != null) {
            copy.next = tmp.next;
            copy = copy.next;
            if(tmp.next != null) {
                tmp.next = tmp.next.next;
            }
            tmp = tmp.next;
        }

    这个剥离的过程也并不复杂，首先将拷贝节点前面的元素指向它后面的元素。然后再将这个拷贝节点往后面跳一个。将上述的几个步骤结合起来，就得到如下的代码：

 

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        RandomListNode copy = head;
        while(copy != null) {
            RandomListNode node = new RandomListNode(copy.label);
            node.next = copy.next;
            copy.next = node;
            copy = node.next;
        }
        copy = head;
        while(copy != null && copy.next != null) {
            if(copy.random != null)
                copy.next.random = copy.random.next;
            copy = copy.next.next;
        }
        copy = head;
        RandomListNode cur  = head.next;
        RandomListNode tmp = cur;
        while(copy != null && tmp != null) {
            copy.next = tmp.next;
            copy = copy.next;
            if(tmp.next != null) {
                tmp.next = tmp.next.next;
            }
            tmp = tmp.next;
        }
        return cur;
    }
}

 

方法二

　　前面讨论的拷贝随机指针的方法虽然效率比较可观，只是推导的思路相对有点复杂。实际上，结合链表的创建和拷贝，我们还有另外一种思路。

　　在不考虑随机指针的情况下，我们只需要在一个链表从头到尾遍历的时候同时创建一个个对应的节点。新链表的创建可以通过创建一个临时节点，它指向新建链表的头节点。这样我们在遍历完链表之后可以找到这个头节点。

　　当然，这样对于一个简单的链表拷贝已经够了。可是还有一些随机链表要考虑。这该怎么解决呢？我们可以在前面遍历原链表的同时建立一个Map，每次将原链表节点和对应新建的节点加入到map中。在创建完包含有next的链表元素之后，我们再一次遍历两个链表。每次遍历原来链表的时候判断它的random指针，如果这个指针非空，则将对应新建链表的random指针指向map里对应的项。

　　于是，按照这个思路，我们可以得到如下的代码：

 

/**
 * 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) {
        RandomListNode l1 = new RandomListNode(0);
        RandomListNode l2 = new RandomListNode(0);
        RandomListNode pre2 = l2;
        l1.next = head;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        while(head != null) {
            RandomListNode copy = new RandomListNode(head.label);
            pre2.next = copy;
            map.put(head, copy);
            head = head.next;
            pre2 = pre2.next;
        }
        head = l1.next;
        pre2 = l2.next;
        while(head != null) {
            if(head.random != null) {
                pre2.random = map.get(head.random);
            }
            head = head.next;
            pre2 = pre2.next;
        }
        return l2.next;
    }
}

 

 

总结

    总的来说，这个问题相对来说复杂一点。因为要构造链表的拷贝，然后调整它们的指针并剥离拷贝的链表出来。从算法本身并不是很复杂，主要是这么多的步骤和指针操作很容易出错，而且很繁琐。需要一点一点的去分析。