java算法题解LeetCode35复杂链表的复制实例

Java算法题解LeetCode35复杂链表的复制实例

题目描述

给定一个链表,除了正常的next指针外,还有一个额外的指针random指向链表中的任意一个节点或者null。请返回这个链表的深度复制。

例如,给定链表1->2->3->4->null,random指针可能指向链表中的任意一个节点,也可能指向null。

解题思路

方法一:哈希表

一个比较暴力的做法是使用哈希表来保存原链表节点和新链表节点之间的对应关系。具体来说,对于原链表中的每个节点,我们创新一个新的节点,并存储在哈希表中,然后我们再次遍历链表,在遍历的过程中处理每个新节点的 next 和 random 指针。

步骤如下:

  1. 遍历链表,将其中的每个节点都存入哈希表中。
  2. 再次遍历链表,对于每个新节点,根据原链表中对应节点的下标,设置新节点的 next 指针和 random 指针。

时间复杂度为O(N),其中N是链表中节点的数量。需要额外的空间来存储哈希表,空间复杂度也为O(N)。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Map<Node, Node> map = new HashMap<>();
    Node newHead = new Node(head.val);
    map.put(head, newHead);
    Node p = head;
    Node q = newHead;
    while (p != null) {
        if (p.next != null) {
            if (!map.containsKey(p.next)) {
                Node newNode = new Node(p.next.val);
                map.put(p.next, newNode);
            }
            q.next = map.get(p.next);
        }
        if (p.random != null) {
            if (!map.containsKey(p.random)) {
                Node newNode = new Node(p.random.val);
                map.put(p.random, newNode);
            }
            q.random = map.get(p.random);
        }
        p = p.next;
        q = q.next;
    }
    return newHead;
}

方法二:原地修改链表

思路是先遍历原链表,对于其中的每一个节点都创建一个新的节点,并将新节点连接到原节点后面。然后再次遍历链表,通过分析原节点的random指针和新节点的next指针的关系,来设置新节点的random指针。

步骤如下:

  1. 遍历链表,对于每一个节点,在该节点之后插入该节点的复制节点。

    原链表:1 -> 2 -> 3
    新链表:1 -> 1' -> 2 -> 2' -> 3 -> 3'

  2. 再次遍历链表,根据原节点的random指针修改新节点的random指针。

    ```
    原链表中的random指针:
    1 -> 3
    2 -> 1
    3 -> 2

    新链表中的random指针:
    1' -> 3'
    2' -> 1'
    3' -> 2'
    ```

  3. 将新链表和原链表分离。

    新链表:1' -> 2' -> 3'
    原链表:1 -> 2 -> 3

时间复杂度为O(N),空间复杂度为O(1)。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node p = head;
    while (p != null) {
        Node newNode = new Node(p.val);
        newNode.next = p.next;
        p.next = newNode;
        p = newNode.next;
    }
    p = head;
    while (p != null) {
        Node newNode = p.next;
        if (p.random != null) {
            newNode.random = p.random.next;
        }
        p = newNode.next;
    }
    p = head;
    Node newHead = head.next;
    while (p != null) {
        Node newNode = p.next;
        p.next = newNode.next;
        if (newNode.next != null) {
            newNode.next = newNode.next.next;
        }
        p = p.next;
    }
    return newHead;
}

示例说明

示例一

输入:1 -> 2 -> null

1 -> null
^
|
2 -> null

输出:1 -> 2 -> null

1 -> null
^
|
2 -> null

示例二

输入:2 -> 1 -> null

2 -> null
^
|
1 -> null

输出:2 -> 1 -> null

2 -> null
^
|
1 -> null
阅读剩余 71%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:java算法题解LeetCode35复杂链表的复制实例 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • ubuntu环境变量设置方法分享

    下面是详细讲解“ubuntu环境变量设置方法分享”的完整攻略。 环境变量是什么 环境变量是操作系统定义的一些全局变量,主要用于在所有进程中存储以供访问的值。在 Ubuntu 中,环境变量通常用于指定一些重要的系统路径和配置信息,例如 PATH、JAVA_HOME 等。 查看当前环境变量 在 Ubuntu 终端中,我们可以使用 echo $PATH 命令查看当…

    other 2023年6月27日
    00
  • Linux内核设备驱动之内核中链表的使用笔记整理

    Linux内核设备驱动之内核中链表的使用笔记整理 1. 简介 在Linux内核中,链表(linked list)是一个常用的数据结构,用于实现不同的数据结构,例如队列、栈、哈希表等。链表的结构相对于数组更加灵活,可以动态地添加和删除元素,但是在访问链表中的元素时需要遍历整个链表,因此访问速度相对较慢。在驱动程序中,链表的使用也很普遍,例如用于管理设备队列、内…

    other 2023年6月27日
    00
  • 战神4进不去怎么办 战神4出现CE-34878-0错误代码解决方法

    标题:战神4进不去怎么办 战神4出现CE-34878-0错误代码解决方法 问题描述 战神4玩家无法进入游戏,并弹出CE-34878-0错误代码提示。该错误代码通常表示游戏发生了无法处理的软件错误,导致程序崩溃。 可能原因 游戏的程序文件出现问题,导致游戏无法正常运行。 系统驱动程序过时或者损坏,导致游戏无法正常运行。 系统过时,可能需要进行更新或者升级。 硬…

    other 2023年6月27日
    00
  • vue将时间戳转换成自定义时间格式的方法

    在Vue中,将时间戳转换成自定义时间格式是一个常见的需求。下面是将时间戳转换成自定义时间格式的完整攻略: 步骤1:安装moment.js 在Vue中,可以使用moment.js库来处理时间。具体步骤如下: 在终端中执行以下命令来安装moment.js: npm install moment — 在Vue组件中引入moment.js: import mome…

    other 2023年5月8日
    00
  • c# TreeView添加右键快键菜单有两种方法

    当我们需要在c# WinForm的TreeView控件上添加右键快捷菜单时,一般有两种方法可以实现。下面详细介绍一下这两种方法: 方法一:使用ContextMenuStrip控件 在TreeView的MouseDown事件中,判断是否右击了鼠标,并添加一个ContextMenuStrip控件。代码如下: private void treeView1_Mous…

    other 2023年6月27日
    00
  • C++中友元类和嵌套类使用详解

    C++中友元类和嵌套类使用详解 在C++中,友元类和嵌套类是两个重要的概念。友元类允许一个类的成员函数或其他类访问该类的私有成员,而嵌套类则是在一个类的内部定义另一个类。下面将详细讲解这两个概念的使用方法,并提供两个示例说明。 友元类(Friend Class) 友元类允许一个类的成员函数或其他类访问该类的私有成员。为了实现友元类,需要在类的声明中使用fri…

    other 2023年7月27日
    00
  • Python 类方法和实例方法(@classmethod),静态方法(@staticmethod)原理与用法分析

    Python 类方法和实例方法原理与用法分析 1. 类方法(@classmethod) 1.1 原理介绍 类方法是在Python中定义在类中的方法,使用@classmethod装饰器来标识。类方法可以访问和修改类属性,也可以通过类来调用,而不需要实例化对象。类方法的第一个参数通常被命名为cls,表示类本身。 1.2 用法示例 下面是一个示例,说明如何定义和使…

    other 2023年6月28日
    00
  • uniapp动态设置’navigationstyle

    以下是“Uniapp动态设置’navigationstyle’”的完整攻略: Uniapp动态设置’navigationstyle’ 在Uniapp中,我们可以使用uni.setNavigationBarStyle方法动态设置导航栏样式。以下是设置导航栏样式的步骤: 1. 设置导航栏样式 首先,我们需要设置导航栏样式。可以使用以下代码: uni.setNav…

    other 2023年5月7日
    00
合作推广
合作推广
分享本页
返回顶部