猿创征文 | 剑指offer 36. 复杂链表的复刻

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：【题目地址】
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

• 函数结束后原链表要与输入时保持一致。

数据范围

链表长度 [0,500]。

方法一：链表 O(n)

这道题其实和普通的链表复制那题比较相似，只是要额外处理一个随机指针：

1. 先将链表所有结点复制一遍，即在原链表中的每个结点都复制一个新的结点。
2. 处理所有 random 指针，从前往后遍历一遍，将复制出来的结点的 random 指针指向对应结点。
3. 将两个链表拆开。

我们来举个例子：

第一步： 将链表所有结点复制一遍。

第二步： 处理所有 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

方法二：哈希表 O(n)

我们可以用哈希表来存储链表中的每个结点，然后串起来：

1. 如果当前结点或当前结点的 random 结点没有被复制过，就复制出来放在哈希表中。
2. 将新链表的指针指向的结点的 next 指针和 next->random 指针指向哈希表中复制的结点。
3. 将两个链表的指针后移一位。

我们还是拿上面那个例子看看：

第一步： 建设一个空的头结点，用来去连接后面新创的结点。

第二步： 创建第一个结点 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

欢迎大家在评论区交流~