LeetCode-剑指 Offer 35. 复杂链表的复制-Java

云惠网小编 2021年12月26日19:18:19
评论
1011字阅读3分22秒
摘要

1.题目请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof2.解法class Solution { public Node copyRandomList(No…

广告也精彩

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

 3.代码

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



2.解法

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;//返回新链表的头结点
}
}

 复制节点

 

2.1 拼接+拆分

 1.题目

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

2.1 拼接+拆分

2.解法

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

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

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

目录

 3.代码

 

 拆分成两个链表

链表图

 

 1.题目

本文转自 https://blog.csdn.net/m0_60494863/article/details/122137767

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论