[Leetcode]138. 复制带随机指针的链表

目录

1.题目链接

2.1解法①(暴力)

2.1.1解法思路：

2.1.2代码实现：

2.2解法②(进阶)

2.1.1解法思路：

2.2.2代码实现：

---

1.题目链接

138. 复制带随机指针的链表 - 力扣（LeetCode）

2.1解法①(暴力)

2.1.1解法思路：

时间复杂度：O(N^2) 空间复杂度O(N); 

①先遍历原链表，复制出一个一模一样的单链表，先不管random的问题；

②然后再遍历新生成的链表，同时进行random指针的拷贝：

这个实现是对于新生成的每一个节点，然后找到原链表的对应的节点，然后遍历原链表找出原链表对应的random指针指向的节点，计算random指向的节点和原链表中对应的节点的相对位置i；

然后在新生成的单链表中找到相同相对位置的节点，然后再将新生成的单链表中的该节点的random指向这个相对位置对应的节点。

2.1.2代码实现：

struct Node* BuyNode(int x)
{
    struct Node* New = (struct Node*)malloc(sizeof(struct Node));
    New->val = x;
    New->next = NULL;
    New->random = NULL;
    return New;
}
 
int CheckList(struct Node* head, struct Node*cur)
{
    int x = 0;
    while(cur->random != head)
    {
        head = head->next;
        x++;
    }
    return x;
}
struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head;
    struct Node* temp = BuyNode(-1);
    struct Node* pre = temp;
    
    //先复制单链表
    while(cur)
    {
        temp->next = BuyNode(cur->val);
        temp = temp->next;
        cur = cur->next;
    }
 
    //复制随机指针
    //1遍历原链表，遇到随即指针不为空的节点；
    //2然后再遍历链表找到随即指针指向的节点，计算位置；
    //3然后放入新的链表中
    temp = pre->next;//初始化新链表箭头
    cur = head;//初始化旧链表指针
    while(cur)
    {
        if(cur->random != NULL)
        {
            int x = CheckList(head, cur);
            struct Node* shead = pre->next;
            for(int i = 0; i < x; i++)
            {
                shead = shead->next;
            }
            temp->random = shead;
        }
        cur = cur->next;
        temp = temp->next;
    }
    return pre->next;
}

---

2.2解法②(进阶)

2.1.1解法思路：

①先进行如下的操作：

在每个节点后面插入一个新的节点然后每个节点的val和前一个节点相同；

 ②然后要做的就是处理新插入节点的random指针，进行第一步的操作就是为了方便第二步来处理random指针的：具体实现的方法就是给定一个指针cur来遍历原来就有的节点，然后遇到random指针不为空的节点，然后就将其next的random指向其的random的next即可；

（这个是最关键的）实现如下的效果；

 ③第三步也是最后一步，然后将那些在原链表上插入的新节点按顺序，尾插成一个新的链表；

2.2.2代码实现：

struct Node* BuyNode(int x)
{
    struct Node* New = (struct Node*)malloc(sizeof(struct Node));
    New->val = x;
    New->next = NULL;
    New->random = NULL;
    return New;
}
 
struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head; 
    //先复制单链表
    while(cur)
    {
        struct Node* cnext = cur->next;
        struct Node* New = BuyNode(cur->val);
        cur->next = New;
        New->next = cnext;
        cur = cur->next->next;
    }
    //给定random
    cur = head;
    while(cur)
    {
        if(cur->random)
        {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //生成新链表
    cur = head;
    struct Node* Bhead = (struct Node*)malloc(sizeof(struct Node));
    Bhead->next = NULL;
    struct Node* tail = Bhead;
    int x = 1;
    while(cur)
    {
        if(x % 2 == 0)
        {
            tail->next = cur;
            tail = tail->next;
        }
        x++;
        cur = cur->next;
    }
 
    return Bhead->next;
}

---

以上就是本博客的所有内容了！