😀前言
在许多实际应用中，我们会遇到复杂链表的复制问题。复杂链表不同于一般的单链表，不仅每个节点有指向下一个节点的指针，还有一个特殊的指针random，可以指向链表中的任意节点或null。如何高效地复制这样一个复杂链表是一个常见的面试题。本文将详细解析这一问题，并提供一个Java实现。
🏠个人主页：尘觉主页
文章目录
- 复杂链表的复制
- 问题描述
- 解题思路
- Java代码实现
- 代码解析
- 关键点解析
- 😄总结
复杂链表的复制
NowCoder
问题描述
给定一个复杂链表，其中每个节点包含一个整型值 label，一个指向下一个节点的指针 next，以及一个指向链表中任意节点的特殊指针 random。我们的任务是返回这个链表的深拷贝，即创建一个新的链表，其结构和原始链表完全相同，但各节点是独立的。
public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}
}
如上图所示，每个节点有两个指针，一个指向下一个节点，另一个随机指向链表中的任意节点或 null。
解题思路
为了高效地复制这个复杂链表，可以分为三个主要步骤：
- 插入复制节点：在每个原节点的后面插入一个新的复制节点。新节点的
label和原节点相同，next指针指向原节点的下一个节点，而原节点的next指针则指向这个新插入的复制节点。
- 建立
random链接：在完成复制节点的插入后，遍历链表，为每个复制节点设置random指针，使其指向原节点random指针指向的节点的下一个节点。
- 拆分链表：最后，将链表拆分为两个独立的链表，一个是原始链表，另一个是复制链表。我们要确保原链表和复制链表的结构和指针完全独立。
Java代码实现
以下是实现这个算法的Java代码，并附有详细的注释解释每一步的操作。
public class Solution {/*** 复制复杂链表* @param pHead 原链表的头节点* @return 复制链表的头节点*/public RandomListNode Clone(RandomListNode pHead) {if (pHead == null) {return null; // 如果原链表为空，直接返回null}// 第一步：在每个节点后面插入复制的节点RandomListNode cur = pHead;while (cur != null) {RandomListNode clone = new RandomListNode(cur.label); // 创建新节点clone.next = cur.next; // 复制节点的next指向原节点的下一个节点cur.next = clone; // 原节点的next指向复制节点cur = clone.next; // 移动到下一个原节点}// 第二步：为复制节点建立 random 链接cur = pHead; // 重置指针到链表头while (cur != null) {RandomListNode clone = cur.next; // 获取复制节点if (cur.random != null) {clone.random = cur.random.next; // 复制节点的random指向原节点的random的下一个节点}cur = clone.next; // 移动到下一个原节点}// 第三步：拆分链表，将复制节点从原链表中分离出来cur = pHead; // 重置指针到链表头RandomListNode pCloneHead = pHead.next; // 记录复制链表的头节点while (cur.next != null) {RandomListNode next = cur.next; // 获取当前节点的下一个节点cur.next = next.next; // 将当前节点的next指针指向下一个原节点cur = next; // 移动到下一个节点}return pCloneHead; // 返回复制链表的头节点}
}代码解析
- 插入复制节点：
- 首先，遍历原始链表，对于每个节点，创建一个新节点，将其插入到当前节点与下一个节点之间。
- 建立
random链接：- 再次遍历链表，为每个复制节点设置
random指针，指向原节点random所指向的节点的下一个节点。
- 再次遍历链表，为每个复制节点设置
- 拆分链表：
- 最后一步，将原链表和复制链表分离。原链表恢复原样，而复制链表则成为一个独立的链表。
关键点解析
- 时间复杂度：
- 整个过程只需遍历链表三次，时间复杂度为 O(N)，其中 N 是链表节点的数量。
- 空间复杂度：
- 由于使用的是原地算法，没有额外的空间开销，空间复杂度为 O(1)。
😄总结
本文介绍了一种高效的算法来解决复杂链表的复制问题。通过在原链表中插入复制节点、建立 random 链接、以及最后的拆分操作，我们可以在O(N)的时间复杂度内完成链表的深拷贝。这种方法不仅简洁高效，而且避免了使用额外的数据结构，是面试中的经典题目之一。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
