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;
   }
}

总结

以上就是本文关于java面试题-实现复杂链表的复制代码分享的全部内容，感兴趣的朋友可以继续参阅：java输出链表倒数第k个节点、java语言实现反转链表代码示例、java编程实现从尾到头打印链表代码实例以及本站其他相关专题，希望对大家有所帮助。如有不足之处，欢迎留言指出，小编一定及时更正，给大家提供更好的阅读体验及帮助，感谢朋友们对本站的支持！