欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-02-23 23:59:34
阿里终面在线编程题,写出来与大家分享一下         有一个单向链表,每个节点都包含一个rand...

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

        有一个单向链表,每个节点都包含一个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编程实现从尾到头打印链表代码实例以及本站其他相关专题,希望对大家有所帮助。如有不足之处,欢迎留言指出,小编一定及时更正,给大家提供更好的阅读体验及帮助,感谢朋友们对本站的支持!