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

目录
  • 题目
    • 示例 1：
    • 示例 2：
    • 示例 3：
    • 示例 4：
  • 解题思路

题目

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

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

提示： -10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。

解题思路

哈希的做法，在大多数公司的面试官面前并不是一个满意的答案，所以需要知道原地修改的解法才能够从容面对面试。 原地修改解法流程： 假设三个节点初始如下

1.第一次遍历，复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null 第一次遍历，构建的节点，random还未连接起来，如下图

我们需要把A指向C，因为初始的A的random指针指向了C，那是不是有这样的公式： A->random = A->random->next

2.第二次遍历，从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在

3.第三次遍历，就比较简单了，只是找出这些相邻节点，组成结果就可以

class Solution {
	public Node copyRandomList(Node head) {
		// if head == null,则return null
		if (head == null) {
			return null;
		}
		// 第一次遍历， 1 -> `1` -> 2 -> `2` -> 3 - > `3` -> null
		Node cur = head;
		while (cur != null) {
			Node node = new Node(cur.val);
			Node temp = cur.next;
			cur.next = node;
			cur.next.next = temp;
			cur = cur.next.next;
		}
		// 第二次遍历，填充random节点
		cur = head;
		while (cur != null) {
			Node newNode = cur.next;
			newNode.random = cur.random != null ? cur.random.next : null;
			cur = cur.next.next;
		}
		// 第三次遍历，拆分
		Node headNew = head.next;
		for (Node node = head; node != null; node = node.next) {
			Node nodeNew = node.next;
			node.next = node.next.next;
			nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
		}
		return headNew;
	}
	class Node {
		int val;
		Node next;
		Node random;
		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}
	}
}

以上就是java算法题解LeetCode35复杂链表的复制实例的详细内容，更多关于java算法复杂链表复制的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java C++刷题leetcode1106解析布尔表达式

    目录 题目 思路:栈[计算器] Java C++ Rust 总结 题目 题目要求 思路:栈[计算器] 和计算器原理类似,分别用两个栈存操作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的. 要注意字母t.f和布尔值true.false的转换. Java class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> tfs = new ArrayDeque<

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • java LeetCode普通字符串模拟题解示例

    目录 题目描述 模拟 最后 题目描述 这是 LeetCode 上的 393. UTF-8 编码验证 ,难度为 中等. Tag : 「模拟」 给定一个表示数据的整数数组 data ,返回它是否为有效的 UTF−8 编码. UTF-8 中的一个字符可能的长度为 1 到 4 字节,遵循以下的规则: 对于 1字节 的字符,字节的第一位设为 0,后面 7 位为这个符号的 unicode 码. 对于 n 字节 的字符 (n>1),第一个字节的前 n 位都设为 1,第 n+1 位设为 0 ,后面字节的前两位一

  • Java C++题解leetcode1620网络信号最好的坐标

    目录 题目 思路:暴力模拟 Java C++ Rust 题目 题目要求 思路:暴力模拟 因为数据范围小,所以是万万没想到的逐个遍历…… 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标. Java class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0,

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

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

  • 剑指Offer之Java算法习题精讲链表专题篇

    剑指Offer之Java算法习题精讲链表专题篇

    题目一  解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solut

  • 剑指Offer之Java算法习题精讲链表与字符串及数组

    剑指Offer之Java算法习题精讲链表与字符串及数组

    题目一 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Soluti

  • 剑指Offer之Java算法习题精讲链表专项训练

    剑指Offer之Java算法习题精讲链表专项训练

    题目一 链表题--链表合并 根据给定的两个升序链表合并为一个新的升序链表 具体题目如下 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;

  • 剑指Offer之Java算法习题精讲链表与数组专项训练

    剑指Offer之Java算法习题精讲链表与数组专项训练

    题目一 数组题——查找目标值 在给定的数组中查找指定的目标值,这里提供两种解法 具体题目如下 解法一 class Solution { public int[] twoSum(int[] nums, int target) { int[] a = {-1,-1}; for(int i = 0;i<nums.length-1;i++){ for(int j = i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ a[0] = i; a[1]

  • 剑指Offer之Java算法习题精讲链表与二叉树专项训练

    剑指Offer之Java算法习题精讲链表与二叉树专项训练

    题目一 链表题——反转链表 根据单链表的头节点head来返回反转后的链表 具体题目如下 解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val;

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • Go Java算法之为运算表达式设计优先级实例

    目录 为运算表达式设计优先级 方法一:动态规划(Java) 方法二:分治(Go) 为运算表达式设计优先级 给你一个由数字和运算符组成的字符串 expression ,按不同优先级组合数字和运算符,计算并返回所有可能组合的结果.你可以 按任意顺序 返回答案. 生成的测试用例满足其对应输出值符合 32 位整数范围,不同结果的数量不超过 104 . 示例 1: 输入:expression = "2-1-1" 输出:[0,2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2 示

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

    C语言复杂链表的复制实例详解

    目录 一.题目描述 示例1: 示例2: 示例3: 示例4: 二.思路分析 三.整体代码 总结 一.题目描述 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例2: 输

随机推荐