Java面试题-实现复杂链表的复制代码分享

阿里终面在线编程题，写出来与大家分享一下

        有一个单向链表，每个节点都包含一个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