题目描述：

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.

题目大意：

给定一个链表，其中的节点包含一个额外的随机指针，可能指向链表中的任意一个节点或者为空。

返回链表的深拷贝。

解题思路：

解法I：时间复杂度O(n)，空间复杂度O(n)

使用哈希表保存原链表到新链表节点的映射，即可实现对随机指针域的拷贝

Python代码：

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        nodeDict = dict()
        dummy = RandomListNode(0)
        pointer, newHead = head, dummy
        while pointer:
            newNode = RandomListNode(pointer.label)
            nodeDict[pointer] = newHead.next = newNode
            newHead, pointer = newHead.next, pointer.next
        pointer, newHead = head, dummy.next
        while pointer:
            if pointer.random:
                newHead.random = nodeDict[pointer.random]
            pointer, newHead = pointer.next, newHead.next
        return dummy.next

解法II：时间复杂度O(n)，空间复杂度O(1)

在原始链表的每一个节点之后插入其自身的拷贝，通过这种方式，即可避免额外空间的使用。

参考LeetCode Discuss：https://leetcode.com/discuss/22421/solution-constant-space-complexity-linear-time-complexity

算法包含下面三个步骤：

1. 遍历原链表，并复制每一个节点，将新节点插入原节点之后

2. 遍历新链表，为其中的新增节点设置random指针

3. 重建原链表，并提取出拷贝的新节点

C++代码：

public RandomListNode copyRandomList(RandomListNode head) {
    RandomListNode iter = head, next;

    // First round: make copy of each node,
    // and link them together side-by-side in a single list.
    while (iter != null) {
        next = iter.next;

        RandomListNode copy = new RandomListNode(iter.label);
        iter.next = copy;
        copy.next = next;

        iter = next;
    }

    // Second round: assign random pointers for the copy nodes.
    iter = head;
    while (iter != null) {
        if (iter.random != null) {
            iter.next.random = iter.random.next;
        }
        iter = iter.next.next;
    }

    // Third round: restore the original list, and extract the copy list.
    iter = head;
    RandomListNode pseudoHead = new RandomListNode(0);
    RandomListNode copy, copyIter = pseudoHead;

    while (iter != null) {
        next = iter.next.next;

        // extract the copy
        copy = iter.next;
        copyIter.next = copy;
        copyIter = copy;

        // restore the original list
        iter.next = next;

        iter = next;
    }

    return pseudoHead.next;
}

 

本文链接：http://bookshadow.com/weblog/2015/07/31/leetcode-copy-list-random-pointer/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码