JZTXT

单链表OJ题解析3 - 复制带随机指针的链表

发布时间 2023-03-24 11:36:04作者: 许木101

 1. 复制带随机指针的链表

题目链接

题目描述

解题思路

首先，解这道题必须要理解链表在内存中的表示

字母表示每一个节点在内存中的起始地址, 每一个节点空间的next 存储下一个节点的地址, random存储随机节点的地址

 

然后理解题目意思, 这道题要求创建一个拷贝链表，每一个拷贝节点的val = 原节点的val,  每一个拷贝节点的random = 原节点random的距离

比如:

原链表节点b的random存储距离为0的节点a, 所以, 拷贝节点i存储拷贝链表的第一个节点h 

 

最后, 实现这个拷贝链表, 返回头结点

第一步，在每一个原结点后链接一个拷贝节点

 

第二步, 在每一个拷贝节点的random上链接原节点的next, 保持相同的相对位置

 

第三步,  把所有的拷贝节点从原链表中拆解下来, 组成一个新链表, 然后还原原链表的链接关系

/**
 * 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* next = cur->next;
        struct Node* copynode = (struct Node*)malloc(sizeof(struct Node));
        copynode->val = cur->val;
        cur->next = copynode;
        copynode->next = next;
        cur = next;
    }
    // 2. 在每一个拷贝节点的random上链接原节点的next, 保持相同的相对位置
    cur = head;
    while (cur)
    {
        struct Node* copynode = cur->next;
        if (NULL == cur->random)
        {
            copynode->random = NULL;
        }
        else 
        {
            copynode->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    // 3. 把所有的拷贝节点从原链表中拆解下来, 组成一个新链表, 然后还原原链表的链接关系
    cur = head;
    struct Node* copyhead = NULL, *copytail = NULL;
    while (cur)
    {
        struct Node* copynode = cur->next;
        struct Node* next = copynode->next;
        if (NULL == copyhead)
        {
            copyhead = copytail = copynode;
        }
        else 
        {
            copytail->next = copynode;
            copytail = copytail->next;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}