当前位置：首页 > news >正文

【LeetCode】剑指 Offer（18）

news 2025/6/30 18:37:59

题目：剑指 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一个新节点，并初始化valNode* 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;}
};