Java面试题-实现复杂链表的复制代码分享
作者:diu_brother 时间:2023-11-23 20:05:39
阿里终面在线编程题,写出来与大家分享一下
有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针。尽可能考虑可能的异常情况。
算法如下:
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
copyNodes(pHead);
setClonedNodes(pHead);
return splitNodes(pHead);
}
//第一步,复制链表任意结点N并创建新结点N‘,再把N'链接到N的后面
public static void copyNodes(RandomListNode head){
RandomListNode temp = head;
while(temp!=null){
RandomListNode clonedNode = new RandomListNode(0);
clonedNode.next = temp.next;
clonedNode.label = temp.label;
clonedNode.random = null;
temp.next = clonedNode;
temp = clonedNode.next;
}
}
//第二步,设置复制出来的结点
public static void setClonedNodes(RandomListNode head){
RandomListNode pNode = head;
while(pNode!=null){
RandomListNode pCloned = pNode.next;
if(pNode.random!=null){
pCloned.random = pNode.random.next;
}
pNode = pCloned.next;
}
}
//第三步,将第二步得到的链表拆分成两个链表
public static RandomListNode splitNodes(RandomListNode head){
RandomListNode pNode = head;
RandomListNode clonedHead = null;
RandomListNode clonedNode = null;
if(pNode!=null){
clonedHead = pNode.next;
clonedNode = pNode.next;
pNode.next = clonedNode.next;
pNode = pNode.next;
}
while(pNode!=null){
clonedNode.next = pNode.next;
clonedNode = clonedNode.next;
pNode.next = clonedNode.next;
pNode = pNode.next;
}
return clonedHead;
}
}
来源:http://blog.csdn.net/diu_brother/article/details/50988968
标签:java,链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
C#使用随机数编写班级点名器的示例代码
2022-05-26 11:04:51
![](https://img.aspxhome.com/file/2023/5/89825_0s.png)
error LNK2019: 无法解析的外部符号 问题的解决办法
2022-07-27 23:02:40
Java深入讲解instanceof关键字的使用
2023-02-27 13:05:05
![](https://img.aspxhome.com/file/2023/8/60998_0s.png)
SpringBoot自动配置源码深入刨析讲解
2022-04-03 14:38:06
![](https://img.aspxhome.com/file/2023/1/86031_0s.png)
Android Support Annotations资料整理
2021-09-21 13:39:33
spring @schedule注解如何动态配置时间间隔
2023-07-29 03:51:14
spring data jpa使用详解(推荐)
2022-06-19 05:22:17
Android实现异步加载图片
2021-08-14 16:44:20
Java注解详细介绍
2021-10-09 19:52:28
C#获取日期的星期名称实例代码
2022-10-22 13:25:53
springmvc @RequestBody String类型参数的使用
2023-03-08 09:30:05
![](https://img.aspxhome.com/file/2023/3/62763_0s.png)
spring多数据源配置实现方法实例分析
2023-06-06 22:15:56
Java中的异常处理用法及其架构和使用建议
2023-02-05 21:27:16
![](https://img.aspxhome.com/file/2023/5/74885_0s.jpg)
Java实现TFIDF算法代码分享
2023-12-23 20:54:45
![](https://img.aspxhome.com/file/2023/7/125497_0s.png)
关于C# Math 处理奇进偶不进的实现代码
2023-03-25 09:30:29
新的Java访问mysql数据库工具类的操作代码
2023-04-05 16:54:58
Filter、Servlet、Listener的学习_动力节点Java学院整理
2021-08-12 00:05:49
![](https://img.aspxhome.com/file/2023/9/72529_0s.jpg)
Spring JPA整合QueryDSL的示例代码
2022-12-02 18:56:22
![](https://img.aspxhome.com/file/2023/1/99891_0s.png)
java中Statement 与 PreparedStatement接口之间的关系和区别
2023-11-25 03:11:11
![](https://img.aspxhome.com/file/2023/9/60029_0s.png)
Android开发使用Drawable绘制圆角与圆形图案功能示例
2023-08-26 21:07:09