力扣 138. 随机链表的复制

简介: 力扣 138. 随机链表的复制

题目描述:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为  null

你的代码 接受原链表的头节点 head 作为传入参数。

思路:

题目要求我们拷贝一个带next指针与random随机访问指针的链表。

如果拷贝一个只带next指针的链表话呢,很简单,根据next依次遍历目标链表,再依次拷贝每个节点的信息就可以了.

一步一步来,我们可以先根据next“这条线” 先拷贝一个新的链表出来。

为什么不是优先根据random指针来拷贝呢?

这是因为random指针指向的是随机节点,可能有环存在,而且,random指向的节点有可能是很后面才出现的节点,而next在题目给出节点目标信息时关系就确定是线性不成环的,所以我们优先考虑拷贝next联系。

如何拷贝各个节点的random联系呢?--本题重点

首先,我们假设每一个random关系是一条有向边,在旧链表中存在random关系(A)-->(B),

那么对应的,我们想让复制出来的新链表也有这么一条边,且为(a)-->(b)

那么如果我们能通过(A)找到(a),通过(B)找到(b),在遍历旧链表的random关系链中,我们就能顺便建立复制体的关系。(其中节点a是A的复制节点,b是B的复制节点)

也就是说,只要我们能通过某种联系找到自己的复制体,那么我们就能复制random联系。

于是题目的关键转移到了如何将这种联系该存下来且能快速找到呢?

根据哈希思想给出以下解法:

解法一:

如果是c++的话,可以用STL库中的map容器来存下旧链节点在新链的复制体节点。

也就是达到hash[A]=a,hash[B]=b.

unordered_map<Node *, Node *> Hash({{NULL, NULL},{head, newhead}});

我这里照顾只学了c语言的朋友,主要讲方法二,不用map容器。

解法二:

改变旧链表的next,使其在被复制完后指向对应的复制体节点。

这里说的复制完是指复制val信息,以及next联系.

在复制next信息时,假设遍历到了A节点,首先用一个临时遍历temp存放A->next。

当我们创造出来了复制体a节点,我们让A->next=a,然后,a->random=A->random.

在将temp里的节点取出来继续遍历。

为什么要 a->random=A->random?

这是因为由于我们已经破坏了目标链表的next关系,我们之后再想复制random关系就不能再遍历旧链表了,仅依靠random关系可能出现环等问题,所以要想复制random关系,我们就要遍历新链表,也就是刚被复制出来的不完全体。

遍历到当前节点a,我们想要找a 的random应该指向哪里,我们可以先找到A的random指向的B,再通过B->next找到b,又因为A的random终点已经被赋给了a->random,所以就有了最重要的一步:

a->random=a->random->next.

这里a->random->next就是指向b节点。

重复以上步骤,就可以将所有random关系复制下来。

解法三:

思路和方法二差不多,只不过是将a->next=A -->next  然后A->next=a.这样一来,在破坏旧链的next关系后我们通过依旧可以通过A->next->next找到原来A的下一个节点。

这样我们再将a->random=A->random->next(先在目标链中找到B,再通过B->next找到b).

这个方法只不过是恢复了旧链的可遍历性而已,和方法二差不多。

代码:

#define _CRT_SECURE_NO_WARNINGS 1
 
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)return NULL;
    struct Node* phead = head;
    struct Node* newhead = (struct Node*)malloc(sizeof(struct Node));//新链的头指针
    struct Node* np = newhead;
    struct Node* star = newhead;
    while (phead) {
        struct Node* t = phead->next;//临时变量,存放phead的下一个节点,防止丢失
        newhead->val = phead->val;
        newhead->random = phead->random;//为了方便后续建立random联系
        phead->next = newhead;//哈希的思想,建立新、旧两个节点的联系
        if (t == NULL) {//如果下一个节点是NULL,就不用开辟空间了
            newhead->next = NULL;
        }
        else {//否则就创造一个节点空间,建立next关系
            newhead->next = (struct Node*)malloc(sizeof(struct Node));
            newhead = newhead->next;
        }
        phead = t;
    }
 
    while (np != NULL) {
        if (np->random != NULL) {
            np->random = np->random->next;//通过旧链找到新链应该指向的节点
        }
        np = np->next;
    }
    return star;
 
}

总结:

这个题总的来说不难,如果想用c写出来的话就要求对链表比较熟悉,还是比较考验基本功滴!

相关文章
|
11天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
11 2
|
7天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
11天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
11天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
11天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
8天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
11天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
11天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II
|
12天前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】