请选择 进入手机版 | 继续访问电脑版

leetcode138 — 复制带随机指针的链表

[复制链接]
唐少琼 发表于 2021-1-3 12:16:47 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题目:

题目链接
思路:
1. 遍历原来的链表并拷贝每一个节点,将拷贝节点放在原来节点的下一个,创造出一个旧节点和新节点交错的链表。
2. 迭代这个新旧节点交错的链表,并用旧节点的 random 指针去更新对应新节点的 random 指针。
3. random 指针已经被赋值给正确的节点, next 指针也需要被正确赋值,以便将新的节点正确链接同时将旧节点重新正确链接。

图示如下:

  1. //如果cur->random不为空,则copyNode->random 为 cur->random->nextif(cur->random)        copyNode->random = cur->random->next;
复制代码

  1. //分开链接    while(cur)    {        Node *copyNode = cur->next;        Node *next = copyNode->next;        cur->next = next;        if(next)            copyNode->next = next->next;        else            //最后一个拷贝结点的next置为NULL            copyNode->next = NULL;        cur = next;    }
复制代码
实现代码:
  1. typedef struct Node Node;struct Node* copyRandomList(struct Node* head) {    if(head == NULL)        return NULL;    Node *cur = head;    //在原链表后拷贝一份    while(cur)    {        Node *copyNode = (Node *)malloc(sizeof(Node));        copyNode->val = cur->val;        copyNode->next = NULL;        copyNode->random = NULL;        Node *next = cur->next;        copyNode->next = next;        cur->next = copyNode;        cur = next;    }    cur = head;    //拷贝random    while(cur)    {        Node *copyNode = cur->next;        if(cur->random)            copyNode->random = cur->random->next;        else            copyNode->random = NULL;        cur = cur->next->next;    }  cur = head;  Node *newnode = head->next;    //分开链接    while(cur)    {        Node *copyNode = cur->next;        Node *next = copyNode->next;        cur->next = next;        if(next)            copyNode->next = next->next;        else            copyNode->next = NULL;        cur = next;    }        return newnode;}
复制代码
来源:https://blog.csdn.net/weixin_45905158/article/details/112058922
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )