LeetCode Copy List with Random Pointer

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.


本题要求对一个链表进行深度拷贝。这个链表有一个特点就是除了有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,居然比前面的还慢。。。

Leave a Reply

Your email address will not be published. Required fields are marked *