【剑指offer35】【C++】复杂链表的复制【利用STL的map&原链表上修改】

题目题解代码

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。

题解

笔记： 首先记住stl map的常用方法：

创建：map<Node*,Node*> m; 插入：m.insert(pair<Node*,Node*>(p,new Node(p->val))); 查找：iter = m.find(node_key); iter->first是key; iter->second是value， 如果没找到有m.find(node_key) == m.end();

关于C++ map的更多操作：https://blog.csdn.net/qq_33216029/article/details/96470266

本题的关键思路：

利用map,key存原节点，value存复制后的节点 首先进行节点的复制，再进行指向关系的复制（包括next,random） 指向关系的复制看上去有点绕，但也容易理解，看成： 【m.find(p)->second】->next =【m.find(p->next)】->second; //m.find(p)->second表示复制后的节点，则其next指向map中key为p->next的复制后的节点，这样复制后的两个节点则构成了next联系

代码

/* // 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==NULL) return NULL; map<Node*,Node*> m;//利用map复制链表，key是原链表，value是复制后的链表 Node* p = head; //复制节点 while(p!=NULL){ m.insert(pair<Node*,Node*>(p,new Node(p->val))); p = p->next; } //复制指向关系next和random p = head; while(p!=NULL){ //m.find(p)代表迭代器iter，iter->first代表原节点，iter->second即表示复制后的节点 if(p->next!=NULL)//防止出现m.find(NULL)报异常，下同 m.find(p)->second->next = m.find(p->next)->second;//m.find(p)->second表示复制后的节点，则其next指向map中key为p->next的复制后的节点 if(p->random!=NULL) m.find(p)->second->random = m.find(p->random)->second; p = p->next; } return m.find(head)->second; } };

在原链表的基础上直接修改的方案（参考力扣评论）

哈希的做法，在大多数公司的面试官面前并不是一个满意的答案，所以需要知道原地修改的解法才能够从容面对面试。 原地修改解法流程：

复制一个新的节点在原有节点之后， 如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null 从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在 将复制完的链表一分为二 根据以上信息，我们不难写出以下代码

原链表的基础上直接修改的代码

class Solution { public: Node* copyRandomList(Node* head) { if(head==NULL) return NULL; //1.复制链表，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null Node* p = head; while(p!=NULL){ Node* cp = new Node(p->val); cp->next = p->next; p->next = cp; p = cp->next; } //2.复制指向关系，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在 p = head; Node* clone_head = p->next; Node* cp; while(p!=NULL){ cp = p->next; if(p->random!=NULL)//p不为空，p->next（复制节点）一定不为空，所以不用判断p->next==null cp->random = p->random->next; p = cp->next; } //3.将链表一分为二 p = head; cp = p->next; while(p!=NULL){ p->next = cp->next; p = p->next; if(p!=NULL){ cp->next = p->next; cp = cp->next; } } return clone_head; } };

关注公众号：【THU小鱼干杂货铺】 不间断分享大厂算法题解、实习面经、学习资料等