138. 复制带随机指针的链表

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 388 阅读时长 ≈ 1 分钟

考点

  • 哈希表与链表的综合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	private:
		unordered_map<Node*, Node*> m;
	public:
		Node* copyRandomList(Node* head) {
			Node *cur = head, *dummyHead = new Node(-1), *curNew = dummyHead;
			while (cur != nullptr) {
				Node *node = new Node(cur->val);
				curNew->next = node;
				curNew = curNew->next;
				m[cur] = node;
				cur = cur->next;
			}
			curNew->next = nullptr;
			cur = head;
			while (cur != nullptr) {
				m[cur]->random = m[cur->random];
				cur = cur->next;
			}
			return dummyHead->next;
		}
};

思路

本题难点就在于，如何保证新链表的random结构与旧链表的random结构完全一样

假设已知旧链表节点A指向节点B，新链表中对应的节点分别为C与D，如何记录C与D的关系？

显然需要使用哈希表来记录新旧节点之间的映射，新节点才可以根据映射来获悉旧节点的指向关系

当然，算法也可以修改为递归

  1. 子问题：创造新节点，连接起来，修改random三个操作

  2. 递归语句顺序：递归方向分为一去一回，去方向到达临界点时返回

    创造新节点可以在去方向完成

    节点连接，修改random必须在回方向完成；因为前者操作需要更新上一个节点的next，后者操作须等待哈希表记录映射关系后

  3. 临界点：当前节点为空

  4. 返回值：当前新节点地址，用以更新上一个节点的next

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
	private:
		unordered_map<Node*, Node*> m;
	public:
		Node* copyRandomList(Node* head) {
			if (head == nullptr) return nullptr;
			Node *node = new Node(head->val);
			m[head] = node;
			node->next = copyRandomList(head->next);
			node->random = m[head->random];
			return node;
		}
};