题解 | #复杂链表的复制#
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ #include <unordered_map> class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return nullptr; RandomListNode* cur=pHead; unordered_map<RandomListNode*, RandomListNode*> map; while (cur) { map[cur] = new RandomListNode(cur->label); cur = cur->next; } cur = pHead; while (cur) { map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } return map[pHead]; } };
使用键值对哈希表unordered_map,首先遍历原链表,建立原链表节点和拷贝链表节点之间的映射关系,然后再建立拷贝节点之间的连接关系,包括Next和random