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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

---

本题要求对一个链表进行深度拷贝。这个链表有一个特点就是除了有value和next指针，还有一个random指针随机指向链表中的一个节点。 我的解法是这样的，使用一个hash表记录每个节点的下标，并且用一个数组array_for_list存储新创建的链表。第一遍扫描只把value和next都复制好，同时记录hash和array_for_list。第二遍扫描时，看看原节点的random是否为空，如果不为空，则去hash表里找其random指向节点的下标pos，同时把新链表的random指向array_for_list[pos]节点。
完整代码如下：

class Solution {
public:
    RandomListNode* copyRandomList(RandomListNode* head)
    {
        unordered_map<RandomListNode*, int> hash;
        vector<RandomListNode*> array_for_list;
        RandomListNode *new_head = new RandomListNode(0), *h1 = head, *h2 = new_head;
        int idx = 0;
        while (h1) {
            hash[h1] = idx++;
            RandomListNode* node = new RandomListNode(h1->label);
            array_for_list.push_back(node);
            h2->next = node;
            h1 = h1->next;
            h2 = h2->next;
        }
        h1 = head;
        h2 = new_head->next;
        while (h1) {
            if (h1->random) {
                h2->random = array_for_list[hash[h1->random]];
            }
            h1 = h1->next;
            h2 = h2->next;
        }
        return new_head->next;
    }
};

本代码提交AC，用时52MS.

二刷。《剑指offer》上有一个类似的题，可以不用额外空间来做，即先对原数组的每个节点都拷贝一个插到原节点的后面，然后对于每一个原节点，新节点的random节点就是原节点random节点的下一个节点。很有意思，可以看《剑指offer》P147，或者看讨论区：https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n/64。
完整代码如下：

class Solution {
public:
    RandomListNode* copyRandomList(RandomListNode* head)
    {
        if (head == NULL)
            return head;
        RandomListNode* iter = head;
        while (iter) {
            RandomListNode* node = new RandomListNode(iter->label);
            node->next = iter->next;
            iter->next = node;
            iter = node->next;
        }
        iter = head;
        while (iter) {
            if (iter->random) {
                iter->next->random = iter->random->next;
            }
            iter = iter->next->next;
        }
        iter = head;
        RandomListNode* copy_head = new RandomListNode(0); // dummy
        RandomListNode *copy_iter = iter->next, *copy_tail = copy_head;
        while (iter) {
            copy_tail->next = copy_iter;
            copy_tail = copy_tail->next;
            iter->next = copy_iter->next;
            iter = iter->next;
            if (iter) {
                copy_iter->next = iter->next;
                copy_iter = copy_iter->next;
            }
        }
        return copy_head->next;
    }
};

本代码提交AC，用时65MS，居然比前面的还慢。。。

三刷。和上面的解法相同，代码更易读：

class Solution {
public:
	Node* copyRandomList(Node* head) {
		if (head == NULL)return NULL;

		// 拷贝主干节点
		Node *l1 = head;
		while (l1 != NULL) {
			Node *cur = new Node(l1->val);
			cur->next = l1->next;
			l1->next = cur;
			l1 = cur->next;
		}

		//连接random指针
		l1 = head;
		while (l1 != NULL) {
			if (l1->random != NULL) {
				l1->next->random = l1->random->next;
			}
			l1 = l1->next->next;
		}

		//拆分
		l1 = head;
		Node *new_head = l1->next;
		Node *l2 = new_head;
		while (l1 != NULL) {
			l1->next = l2->next;
			if (l1->next != NULL) {
				l2->next = l1->next->next;
			}
			l1 = l1->next;
			l2 = l2->next;
		}
		return new_head;
	}
};

本代码提交AC，用时8MS。