温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetcode如何实现复制带随机指针的链表

发布时间:2021-12-16 09:34:08 来源:亿速云 阅读:128 作者:小新 栏目:大数据

小编给大家分享一下leetcode如何实现复制带随机指针的链表,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

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

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

示例:

leetcode如何实现复制带随机指针的链表

输入:

{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。

提示:

  1. 你必须返回给定头的拷贝作为对克隆列表的引用。

解题技巧:

1,因为random指针的存在,所以copy的时候如何定位random是个问题,所以简单方法在原链表每个位置后面插入一个元素。

2,由于random可能指向前面的指针,所以复制完之前不能拆解

3,注意边界条件,对于指针类题目,一定要判断空情况

/*// Definition for a Node.class Node {public:    int val;    Node* next;    Node* random;
   Node() {}
   Node(int _val, Node* _next, Node* _random) {        val = _val;        next = _next;        random = _random;    }};*/class Solution {public:    Node* copyRandomList(Node* head) {       Node* h=NULL;        Node* t=NULL;        Node* cur=NULL;        cur=head;       while(cur!=NULL){            t=cur->next;            cur->next=new Node(cur->val,t,NULL);           cur=t;       }            cur=head;        if (cur==NULL){            return NULL;        }        h=cur->next;        t=h;         while(cur!=NULL){             if (cur->random!=NULL){             t->random=cur->random->next;             }             cur=t->next;             if (cur!=NULL){                  t=cur->next;             }         }                cur=head;        h=cur->next;        t=h;        while(cur!=NULL){              cur->next=t->next;               cur=cur->next;               if (cur!=NULL){                 t->next=cur->next;                 t=t->next;               }         }
       return h;    }};

以上是“leetcode如何实现复制带随机指针的链表”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI