阿里终面在线编程题，写出来与大家分享一下
有一个单向链表，每个节点都包含一个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;
}
}
总结
以上就是本文关于java面试题-实现复杂链表的复制代码分享的全部内容，感兴趣的朋友可以继续参阅：java输出链表倒数第k个节点、java语言实现反转链表代码示例、java编程实现从尾到头打印链表代码实例以及本站其他相关专题，希望对大家有所帮助。如有不足之处，欢迎留言指出，小编一定及时更正，给大家提供更好的阅读体验及帮助，感谢朋友们对本站的支持！
如对本文有疑问， 点击进行留言回复！！
IntelliJ IDEA 自定义控制台输出多颜色格式功能 --- 安装Grep Console插件
2020苹果cmsv10非海螺模板苹果cms模板苹果cms10好看的模板带多功能后台
JavaWeb阶段 - Cookie与Session学习总结
网友评论