Java实现复杂链表的复制代码分享-java教程-PHP中文网

Java实现复杂链表的复制代码分享

黄舟

发布： 2017-10-17 10:06:15

原创

1457 人浏览过

这篇文章主要介绍了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&#39;链接到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实现复杂链表的复制代码分享的详细内容。更多信息请关注PHP中文网其他相关文章！