题目描述
请实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。
注意：
- 函数结束后原链表要与输入时保持一致。
数据范围
链表长度 [0,500]。
方法一：链表 O(n)
这道题其实和普通的链表复制那题比较相似，只是要额外处理一个随机指针：
- 先将链表所有结点复制一遍，即在原链表中的每个结点都复制一个新的结点。
- 处理所有
random指针，从前往后遍历一遍，将复制出来的结点的random指针指向对应结点。 - 将两个链表拆开。
我们来举个例子：
第一步： 将链表所有结点复制一遍。
第二步： 处理所有 random 指针。
第三步： 再将链表拆开。
/** * Definition for singly-linked list with a random pointer. * struct ListNode { * int val; * ListNode *next, *random; * ListNode(int x) : val(x), next(NULL), random(NULL) {} * }; */ class Solution { public: ListNode* copyRandomList(ListNode* head) { //先复制一遍结点 for (auto p = head; p;) { auto np = new ListNode(p->val); np->next = p->next; p->next = np; p = np->next; } //再改变所有random指针 for (auto p = head; p; p = p->next->next) { if (p->random != NULL) p->next->random = p->random->next; } //开始将两个链表拆开 auto dummy = new ListNode(-1); auto cur = dummy; for (auto p = head; p; p = p->next) { cur->next = p->next; cur = cur->next; p->next = p->next->next; } return dummy->next; } };
方法二：哈希表 O(n)
我们可以用哈希表来存储链表中的每个结点，然后串起来：
如果当前结点或当前结点的 random 结点没有被复制过，就复制出来放在哈希表中。
将新链表的指针指向的结点的 next 指针和 next->random 指针指向哈希表中复制的结点。
将两个链表的指针后移一位。
我们还是拿上面那个例子看看：
第一步： 建设一个空的头结点，用来去连接后面新创的结点。
第二步： 创建第一个结点 7 和它 random 指向的结点，将创建的结点位置用哈希表存起来，这样下次用到这个结点时就直接取，不用再创建。
第三步： 创建第二个结点，但是第二个结点 random 指向的结点 7 已经被创建过，所以直接在哈希表中查找即可。
第四步： 第三个结点也被创建过，所以只用创建其 random 指向的结点 1 。
第五步： 第四个结点没被创建，但是其 random 指向的结点 1 已经被创建，直接使用即可。
第六步： 所需结点都已经被创建，直接连接结点即可，得到最终结果。
/*/** * Definition for singly-linked list with a random pointer. * struct ListNode { * int val; * ListNode *next, *random; * ListNode(int x) : val(x), next(NULL), random(NULL) {} * }; */ class Solution { public: ListNode* copyRandomList(ListNode* head) { unordered_map<ListNode*, ListNode*> hash; hash[NULL] = NULL; auto dummy = new ListNode(-1), tail = dummy; while (head) { //将没有复制过的结点进行复制，放到哈希表中 if (!hash.count(head)) hash[head] = new ListNode(head->val); if (!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val); tail->next = hash[head]; tail->next->random = hash[head->random]; tail = tail->next; head = head->next; } return dummy->next; } };
欢迎大家在评论区交流~
