阿里终面在线编程题,写出来与大家分享一下
有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针。尽可能考虑可能的异常情况。
算法如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
/*
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面试题-实现复杂链表的复制代码分享的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出,小编一定及时更正,给大家提供更好的阅读体验及帮助,感谢朋友们对本站的支持!
原文链接:http://blog.csdn.net/diu_brother/article/details/50988968