目录

题目：剑指 Offer 35. 复杂链表的复制 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 35. 复杂链表的复制 - 力扣（Leetcode）

题目的接口：

/*// Definition for a Node.class Node {public:    int val;    Node* next;    Node* random;        Node(int _val) {        val = _val;        next = NULL;        random = NULL;    }};*/class Solution {public:    Node* copyRandomList(Node* head) {    }};

解题思路：

一开始先判断一下链表是否为空，

如果为空，直接返回空就行。

接下来是思路：

我的思路是通过原链表再复制一个链表：

 所以我们的第一步就是循环创建一个链表，

接在原链表上，如上图，

然后，

第二步是将原链表的random指针同样复制到新的链表上，

（改random的图我懒得画了，如果感兴趣可以自己画一画）

最后一步就是将新的链表独立出来，

再让原链表恢复，如下图：

 最后再返回新的链表的头结点即可。

代码如下：

代码：

/*// Definition for a Node.class Node {public:    int val;    Node* next;    Node* random;        Node(int _val) {        val = _val;        next = NULL;        random = NULL;    }};*/class Solution {public:    Node* copyRandomList(Node* head) {        //判断链表是否为空        if(!head)        {            return nullptr;        }        //复制原链表        Node* cur = head;        while(cur)        {            //new一个新节点，并初始化val            Node* copy = new Node(cur->val);            copy->next = cur->next;            cur->next = copy;            cur = copy->next;        }        //复制原链表的指针        cur = head;        while(cur)        {            //如果randam是指向空指针就不用管（因为原本就是空）            if(cur->random)            {                cur->next->random = cur->random->next;            }            cur = cur->next->next;        }        //将原链表还原，将新链表独立出来        Node* newhead = head->next;        Node* prev = head;        cur = newhead;        while(cur->next)        {            //还原原链表            prev->next = prev->next->next;            prev = prev->next;            //独立新链表            cur->next = cur->next->next;            cur = cur->next;        }        //新链表的尾        prev->next = nullptr;        //返回新链表的头        return newhead;    }};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。