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

力扣链接

思路一:

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

思路二:

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

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

思路三:

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

将每个原结点复制,

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

//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

例如: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;
}