题解 | #复杂链表的复制#

class Solution {
public:
	RandomListNode* Clone(RandomListNode* pHead) {
		//hash表，用于记录旧节点对应的新节点是否已经开辟，同时建立两者的联系
		unordered_map< RandomListNode*, RandomListNode*>m;
		RandomListNode*p = pHead;
		//第一部分，首先根据next开辟所有需要的新节点
		while (p != NULL) {
			//没有新节点，那么创建一个
			if(m.count(p)==0)m[p] = new RandomListNode(p->label);
			//将next指针配好
			if (p->next == NULL)m[p]->next = NULL;
			else {
				if (m.count(p->next) == 0)m[p->next] = new RandomListNode(p->next->label);
				m[p]->next = m[p->next];
			}
			p = p->next;
		}
		//第二部分，将所有random指针连接好
		p = pHead;
		while (p != NULL) {
			if (p->random == NULL) {
				m[p]->random = NULL;
			}
			else {
				m[p]->random = m[p->random];
			}
			p = p->next;
		}

		//返回新链表的头节点
		return m[pHead];//这里就可以明显看出建立map的重要性啦，可以直接根据旧节点找到新节点
	}
};