[leetcode]复制带随机指针的链表

奋斗吧
奋斗吧
擅长邻域：未填写

标签： [leetcode]复制带随机指针的链表 C/C++博客 51CTO博客

2023-04-27 18:23:53 187浏览

[leetcode]复制带随机指针的链表，力扣链接思路一:遍历链表,将链表结点复制下来,控制随机指针,去找对应的第几个(相对位置)进行链接.思路二:以时间换空间,创建两个指针数组,分别存放两个链表中结点的地址,直接可以在指针数组中找到结点该方法比上面的方法更优,但是时间复杂度依旧很高,但是还是达不到O(N)思路三:1.拷贝结点链接在原结点后面将每个原结点复制,将复制后得到的结点分别链接到原结点的后面//1.插入拷贝结点在原结点的后面

力扣链接

[leetcode]复制带随机指针的链表_结点

思路一:

遍历链表,将链表结点复制下来,控制随机指针,去找对应的第几个(相对位置)进行链接.

[leetcode]复制带随机指针的链表_结点_02

思路二:

以时间换空间,创建两个指针数组,分别存放两个链表中结点的地址,直接可以在指针数组中找到结点

该方法比上面的方法更优,但是时间复杂度依旧很高,但是还是达不到O(N)


思路三:

[leetcode]复制带随机指针的链表_链表_03

1.拷贝结点链接在原结点后面

将每个原结点复制,

将复制后得到的结点分别链接到原结点的后面

[leetcode]复制带随机指针的链表_结点_04

//1.插入拷贝结点在原结点的后面
    struct Node* cur = head;
    while(cur)
    {
        //插入
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        struct Node* next = cur->next;

        //链接
        cur->next = copy;
        copy->next = next;

        cur = next;
    }

2.拷贝结点的random是原结点random的next

[leetcode]复制带随机指针的链表_结点_05

例如:13的random是7,7的random->next是拷贝的7

而拷贝的13的random刚好是拷贝的7

//处理拷贝的结点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;


        }


        cur = cur->next->next;
    }

3.拷贝结点解下来,连接成一个新链表,原链表恢复

将拷贝的链表尾插成新链表


//拷贝结点解下来,连接成新链表,并且恢复原链表
    //这里选择不带哨兵位头结点的尾插
    struct Node* copyhead = NULL,*copyTail = NULL;//定义了新链表头copyhead和尾copyTail
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;


        //copy尾插
        if(copyhead == NULL)
        {
            copyhead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;


        }


        //恢复原链表
        cur->next = next;


        cur = next;


    }
    return copyhead;
}

完整代码:

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


struct Node* copyRandomList(struct Node* head) 
{
    //1.插入拷贝结点在原结点的后面
    struct Node* cur = head;
    while(cur)
    {
        //插入
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        struct Node* next = cur->next;


        //链接
        cur->next = copy;
        copy->next = next;


        cur = next;
    }
    



    //处理拷贝的结点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;


        }


        cur = cur->next->next;
    }


    //拷贝结点解下来,连接成新链表,并且恢复原链表
    //这里选择不带哨兵位头结点的尾插
    struct Node* copyhead = NULL,*copyTail = NULL;
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;


        //copy尾插
        if(copyhead == NULL)
        {
            copyhead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;


        }


        //恢复原链表
        cur->next = next;


        cur = next;


    }
    return copyhead;
}




好博客就要一起分享哦！分享海报

此处可发布评论

评论（0）展开评论

暂无评论，快来写一下吧

展开评论

您可能感兴趣的博客

客服QQ 1913284695