当前位置：首页 > news >正文

随机链表的复制问题详解与代码实现

news 2025/5/23 12:58:18

一、问题描述

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

题目要求对一个带有随机指针（random）的链表进行深拷贝。深拷贝的规则是：

新建与原链表长度相同的全新节点，值与原节点对应相同。
新节点的next和random指针需指向复制链表中的新节点，且指针指向关系与原链表完全一致，不能指向原链表节点。

输入为原链表头节点，输出为复制链表的头节点。示例输入输出如下：

示例 1：
- 输入：[[7,null], [13,0], [11,4], [10,2], [1,0]]
- 输出：[[7,null], [13,0], [11,4], [10,2],[1,0]]

二、代码实现与详解

（一）链表节点定义

struct Node {int val;struct Node *next;struct Node *random;
};

（二）在原链表每个节点后插入copy

Node* cur = head;while(cur){Node* copy = (Node*)malloc(sizeof(Node));if(copy == NULL){perror("malloc fail!");exit(1);}copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}

（三）控制random

 cur = head;while(cur){Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}

（四）尾插连接copy,恢复原链表

Node* copyhead = NULL, *copytail = NULL;cur = head;while(cur){Node* copy = cur->next;Node* next = copy->next;if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}cur->next = next;cur = next;}return copyhead;

三、扩展思考

高效解法：哈希表映射法

核心思想

通过哈希表建立原节点与新节点的一一映射关系，确保在复制过程中能快速找到对应新节点，从而正确设置random指针。

步骤分解

第一次遍历：创建新节点并建立映射
遍历原链表，为每个原节点创建对应的新节点，将原节点作为键、新节点作为值存入哈希表。
第二次遍历：设置新节点的next和random指针
再次遍历原链表，通过哈希表获取当前原节点对应的新节点，以及原节点next和random指向的原节点对应的新节点，完成指针赋值。