【数据结构OJ题】复制带随机指针的链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构OJ题】复制带随机指针的链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

1. 题目描述

2. 思路分析

3. 代码实现

1. 题目描述

【数据结构OJ题】复制带随机指针的链表,数据结构,数据结构,链表,c语言,leetcode

2. 思路分析

此题可以分三步进行：
1. 拷贝链表的每一个结点，拷贝的结点先链接到被拷贝结点的后面。
2. 复制随机指针的链接：拷贝结点的随机指针指向被拷贝结点随机指针的下一个位置。
3. 拆解链表，把拷贝的链表从原链表中拆解出来。

3. 代码实现

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head;
    while(cur)
    {
        struct Node* next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
            copy->random=NULL;
        else
            copy->random=cur->random->next;
        
        cur=copy->next;
    }
    cur=head;
    struct Node* copyhead=NULL,*copytail=NULL;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(copytail==NULL)
            copyhead=copytail=copy;
        else
        {
            copytail->next=copy;
            copytail=copytail->next;
        }
        cur->next=next;
        cur=next;
    }
    return copyhead;
}

【数据结构OJ题】复制带随机指针的链表,数据结构,数据结构,链表,c语言,leetcode 文章来源地址https://www.toymoban.com/news/detail-656631.html