Java复杂链表的复制详解

目录
  • 1.题目
  • 2.解法
    • 2.1 拼接+拆分
  • 3.代码

1.题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

2.解法

2.1 拼接+拆分

首先我们逐个将节点复制并且和原来的链表连起来得新链表；

然后再构建新链表的random 指向。当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next

将得到的新链表之间的复制节点拆分出来连成一个复制链表，拆分成原链表和复制链表。

链表图

复制节点

将复制节点的random.next 连接起来

拆分成两个链表

3.代码

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        //1.复制各个链表，并连接
        Node cur = head;
        while (cur != null) {
            //复制
            Node prev = new Node(cur.val);
            prev.next = cur.next;
            //连接
            cur.next = prev;
            //往后走
            cur = prev.next;
        }
        //2.构建各新节点的random 指向
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //3.拆分复制的链表
        cur = head.next;
        Node node = head;
        Node nodeNext = head.next;
        while (cur.next != null) {
            node.next = node.next.next;
            cur.next = cur.next.next;
            node = node.next;
            cur = cur.next;
        }
        node.next = null;//尾节点
        return nodeNext;//返回新链表的头结点
    }
}

到此这篇关于Java复杂链表的复制详解的文章就介绍到这了,更多相关Java 复杂链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java面试题-实现复杂链表的复制代码分享

    阿里终面在线编程题,写出来与大家分享一下 有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针.尽可能考虑可能的异常情况. 算法如下: /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.labe

  • Java实现链表数据结构的方法

    Java实现链表数据结构的方法

    什么是链表? 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的.每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址). 链表的理解示意图: 链表的特点是什么? 获取数据麻烦,需要遍历查找,比数组慢方便插入.删除 简单的链表的实现原理 创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指

  • Java数据结构与算法学习之循环链表

    Java数据结构与算法学习之循环链表

    目录 存储结构示意图 初始化循环链表  循环链表的插入 首位置 代码实现 其他位置 代码实现(总) 循环链表的删除 1.操作的为第一个元素 2.操作元素不为第一个元素 代码实现(总) 循环链表的常见操作  存储结构示意图 优点 : 能够通过任意结点遍历整个链表结构 初始化循环链表  1.循环链表的结点 typedef struct CircularNode { ElementType date; //数据域 struct CircularNode* next; //指向下一个结点的指针域 }Ci

  • Java实现无头双向链表操作

    Java实现无头双向链表操作

    本文实例为大家分享了Java实现无头双向链表的具体代码,供大家参考,具体内容如下 无头双向链表的结构: 代码分析 节点结构 class Node {     private int data;     private Node next;     private Node prev;     public Node(int data) {         this.data = data;         this.prev = null;         this.next = null;  

  • Java 数据结构之删除链表中重复的结点

    Java 数据结构之删除链表中重复的结点

    目录 解析一:(不提倡) 解析二:(正解) 核心考点:链表操作,临界条件检查,特殊情况处理 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针. 解析一:(不提倡) 解决该问题较简单,且在写代码时不易出错的做法如下: 遍历一遍链表,记录重复结点的结点值. 再遍历一遍链表,逐个删除重复结点. 动图演示: 该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡. /* struct ListNode { int val; st

  • Java数据结构与算法学习之双向链表

    Java数据结构与算法学习之双向链表

    目录 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 2.双向链表的头结点 3.总代码 双向链表中的指定文件插入元素  1.插入的为第一个位置 2.其他位置插入 总代码 双向链表的删除 1.删除第一个元素 2.删除其他位置元素 总代码 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 代码实现 //双向链表的结点,包含一个数据域,两个指针域 typedef struct DoublyNode { ElementType date; //数据域 struct

  • Java实现单链表的操作

    Java实现单链表的操作

    本文实例为大家分享了Java实现单链表的基本操作,供大家参考,具体内容如下 顺序表:物理上逻辑上都连续:链表:物理上不一定连续,逻辑上一定连续的. 链表的概念及结构 概念:连表示一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的. 8种链表结构: 单项.双向带头.不带头循环.非循环 主要的三种链表: 无头单项非循环链表.带头循环单链表.不带头双向循环链表 代码实现 1. 接口定义 package com.github.linked.Impl; publ

  • java单链表实现书籍管理系统

    本文实例为大家分享了java单链表实现书籍管理系统的具体代码,供大家参考,具体内容如下 书籍管理系统功能: 1).添加图书 2).删除图书 3).查看图书 4).修改书籍 5).修改排序方式 6).模糊查询 7).退出程序 代码实现: Book类 package com.bookmanagement.book; public class Book {//书类 public String no; public String name; public int price; public String

  • 带你了解Java数据结构和算法之链表

    带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • Java复杂链表的复制详解

    Java复杂链表的复制详解

    目录 1.题目 2.解法 2.1 拼接+拆分 3.代码 1.题目 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 2.解法 2.1 拼接+拆分 首先我们逐个将节点复制并且和原来的链表连起

  • C语言之复杂链表的复制详解

    C语言之复杂链表的复制详解

    什么是复杂链表? 复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点.今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表. 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct Complex

  • Java合并两个及以上有序链表的示例详解

    目录 题目一:合并两个有序链表 题目一思路 题目一完整代码 题目二:合并多个有序链表 题目二关键思路 题目二完整代码 题目一:合并两个有序链表 题目链接 题目一思路 设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头. 首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以. 这样,我们就设置好了要返回链表的头节点,假设头节点是head, 依次移动t1和t2指针,谁小,谁就接入进来.依次操作,直到两个链

  • java集合中的list详解

    1.List接口 该接口定义的元素是有序的且可重复的.相当于数学里面的数列,有序可重复 booleanaddAll(intindex,Collection<?extendsE>c);将指定集合中所有元素,插入至本集合第index个元素之后defaultvoidreplaceAll(UnaryOperatoroperator);替换集合中每一个元素值defaultvoidsort(Comparator<?superE>c);给集合中的元素进行排序Eget(intindex);获取集合

  • Java基础之容器Vector详解

    一.前言 知识补充:Arrays.copyOf函数: public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } 可见copyOf()在内部新建一个数组,调用arrayCopy()将ori

  • JAVA中string数据类型转换详解

    在JAVA中string是final类,提供字符串不可以修改,string类型在项目中经常使用,下面给大家介绍比较常用的string数据类型转换: String数据类型转换成long.int.double.float.boolean.char等七种数据类型 复制代码 代码如下: * 数据类型转换 * @author Administrator * */ public class 数据类型转换 { public static void main(String[] args) { String c=

  • java 深拷贝与浅拷贝机制详解

     java 深拷贝与浅拷贝机制详解 概要: 在Java中,拷贝分为深拷贝和浅拷贝两种.java在公共超类Object中实现了一种叫做clone的方法,这种方法clone出来的新对象为浅拷贝,而通过自己定义的clone方法为深拷贝. (一)Object中clone方法 如果我们new出一个新对象,用一个声明去引用它,之后又用另一个声明去引用前一个声明,那么最后的结果是:这两个声明的变量将指向同一个对象,一处被改全部被改.如果我们想创建一个对象的copy,这个copy和对象的各种属性完全相同,而且修

  • Linux server配置安装Java与Tomcat服务器教程详解

    系统:Ubuntu 16.04 dev_desktop 1.Java安装并配置环境变量 (1)从Java官方网站下载最新版JDK: http://www.oracle.com/technetwork/java/javase/downloads/index.html 下载jdk压缩包 jdk-8u144-linux-x64.tar.gz (2)  将压缩包解压并复制到/usr/lib 目录下 tar -zxvf jdk-8u144-linux-x64.tar.gz sudo cp -r ./jdk

  • java LRU(Least Recently Used )详解及实例代码

    java LRU(Least Recently Used )详解 LRU是Least Recently Used 的缩写,翻译过来就是"最近最少使用",LRU缓存就是使用这种原理实现,简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉,比如我们缓存10000条数据,当数据小于10000时可以随意添加,当超过10000时就需要把新的数据添加进来,同时要把过期数据删除,以确保我们最大缓存10000条,那怎么确定删除哪条过期数据呢,采用LRU算法实现的话就是将最老的数据

  • 基于java中集合的概念(详解)

    1.集合是储存对象的,长度可变,可以封装不同的对象 2.迭代器: 其实就是取出元素的方式(只能判断,取出,移除,无法增加) 就是把取出方式定义在集合内部,这样取出方式就可以直接访问集合内部的元素,那么取出方式就被定义成了内部类. 二每一个容器的数据结构不同,所以取出的动作细节也不一样.但是都有共性内容判断和取出,那么可以将共性提取,这些内部类都符合一个规则Iterator Iterator it = list.iterator(); while(it.hasNext()){ System.out

随机推荐