「复制带随机指针的链表」的一个很巧妙解法

「复制带随机指针的链表」的一个很巧妙解法

题目来源于 LeetCode 上第 138 号问题:复制带随机指针的链表。题目难度为 Medium,目前通过率为 40.5% 。

题目描述

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝

题目解析

  1. 在原链表的每个节点后面拷贝出一个新的节点

  2. 依次给新的节点的随机指针赋值:cur->next->random = cur->random->next

  3. 断开链表可得到深度拷贝后的新链表

之所以说这个方法比较巧妙是因为相较于一般的解法(如使用 Hash map )来处理,上面这个解法 不需要占用额外的空间

动画描述

「复制带随机指针的链表」的一个很巧妙解法

代码实现

我发现带指针的题目使用 C++ 版本更容易描述,所以下面的代码实现是 C++ 版本。

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return NULL;
        RandomListNode *cur = head;
        while (cur) {
            RandomListNode *node = new RandomListNode(cur->label);
            node->next = cur->next;
            cur->next = node;
            cur = node->next;
        }
        cur = head;
        while (cur) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        cur = head;
        RandomListNode *res = head->next;
        while (cur) {
            RandomListNode *tmp = cur->next;
            cur->next = tmp->next;
            if(tmp->next) tmp->next = tmp->next->next;
            cur = cur->next;
        }
        return res;
    }
};

推荐阅读

拜托,面试官别问我「布隆」了

数据结构与算法:三十张图弄懂「图的两种遍历方式」

昨天,终于拿到了腾讯 offer

几道和「二叉树」有关的算法面试题

几道和散列(哈希)表有关的面试题

一道看完答案你会觉得很沙雕的「动态规划算法题」

几道和「堆栈、队列」有关的面试算法题

链表算法面试问题?看我就够了!


「复制带随机指针的链表」的一个很巧妙解法

欢迎关注「复制带随机指针的链表」的一个很巧妙解法

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 「复制带随机指针的链表」的一个很巧妙解法

我还会在以下平台发布内容

GitHub 哔哩哔哩