Java面试题-实现复杂链表的复制代码分享
阿里终面在线编程题，写出来与大家分享一下
有一个单向链表，每个节点都包含一个random指针，指向本链表中的某个节点或者为空，写一个深度拷贝函数，拷贝整个链表，包括random指针。尽可能考虑可能的异常情况。
算法如下：
/*
publicclassRandomListNode{
intlabel;
RandomListNodenext=null;
RandomListNoderandom=null;
RandomListNode(intlabel){
this.label=label;
}
}
*/
publicclassSolution{
publicRandomListNodeClone(RandomListNodepHead)
{
copyNodes(pHead);
setClonedNodes(pHead);
returnsplitNodes(pHead);
}
//第一步，复制链表任意结点N并创建新结点N‘，再把N'链接到N的后面
publicstaticvoidcopyNodes(RandomListNodehead){
RandomListNodetemp=head;
while(temp!=null){
RandomListNodeclonedNode=newRandomListNode(0);
clonedNode.next=temp.next;
clonedNode.label=temp.label;
clonedNode.random=null;
temp.next=clonedNode;
temp=clonedNode.next;
}
}
//第二步，设置复制出来的结点
publicstaticvoidsetClonedNodes(RandomListNodehead){
RandomListNodepNode=head;
while(pNode!=null){
RandomListNodepCloned=pNode.next;
if(pNode.random!=null){
pCloned.random=pNode.random.next;
}
pNode=pCloned.next;
}
}
//第三步，将第二步得到的链表拆分成两个链表
publicstaticRandomListNodesplitNodes(RandomListNodehead){
RandomListNodepNode=head;
RandomListNodeclonedHead=null;
RandomListNodeclonedNode=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;
}
returnclonedHead;
}
}
总结
以上就是本文关于Java面试题-实现复杂链表的复制代码分享的全部内容，感兴趣的朋友可以继续参阅：Java输出链表倒数第k个节点、Java语言实现反转链表代码示例、Java编程实现从尾到头打印链表代码实例以及本站其他相关专题，希望对大家有所帮助。如有不足之处，欢迎留言指出，小编一定及时更正，给大家提供更好的阅读体验及帮助，感谢朋友们对本站的支持！