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

赞 (0)

相关推荐

  • java 中链表的定义与使用方法

    java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my

  • java 实现单链表逆转详解及实例代码

    java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o

  • Java实现单链表翻转实例代码

    Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

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

    阿里终面在线编程题,写出来与大家分享一下 有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针.尽可能考虑可能的异常情况. 算法如下: /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.labe

  • java编程实现优先队列的二叉堆代码分享

    这里主要介绍的是优先队列的二叉堆Java实现,代码如下: package practice; import edu.princeton.cs.algs4.StdRandom; public class TestMain { public static void main(String[] args) { int[] a = new int[20]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*1

  • Java实现JS中的escape和UNescape代码分享

    众所周知,JavaScript中escape() 函数可对字符串进行编码,这样就可以在所有的计算机上读取该字符串.下面,我们就来看看 Java语言中类似JavaScript中的escape() 和unescape() 转码方法,具体代码如下: public class EscapeUnescape { public static String escape(String src) { int i; char j; StringBuffer tmp = new StringBuffer(); tm

  • java实现遍历树形菜单两种实现代码分享

    文本主要向大家分享了java实现遍历树形菜单的实例代码,具体如下. OpenSessionView实现: package org.web; import java.io.IOException; import javax.servlet.Filter; import javax.servlet.FilterChain; import javax.servlet.FilterConfig; import javax.servlet.ServletException; import javax.se

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • Java设计模式之代理模式原理及实现代码分享

    简介 Java编程的目标是实现现实不能完成的,优化现实能够完成的,是一种虚拟技术.生活中的方方面面都可以虚拟到代码中.代理模式所讲的就是现实生活中的这么一个概念:中介. 代理模式的定义:给某一个对象提供一个代理,并由代理对象控制对原对象的引用. 代理模式包含如下角色: ISubject:抽象主题角色,是一个接口.该接口是对象和它的代理共用的接口. RealSubject:真实主题角色,是实现抽象主题接口的类. Proxy:代理角色,内部含有对真实对象RealSubject的引用,从而可以操作真实

  • java检查服务器的连通两种方法代码分享

    首先要了解一下ping的内容. 概述 PING (Packet Internet Groper),因特网包探索器,用于测试网络连接量的程序.Ping发送一个ICMP(Internet Control Messages Protocol)即因特网信报控制协议:回声请求消息给目的地并报告是否收到所希望的ICMPecho (ICMP回声应答).它是用来检查网络是否通畅或者网络连接速度的命令.作为一个生活在网络上的管理员或者黑客来说,ping命令是第一个必须掌握的DOS命令,它所利用的原理是这样的:利用

  • Java使用poi包读取Excel文档代码分享

    项目需要解析Excel文档获取数据,就在网上找了一些资料,结合自己这次使用,写下心得: 1.maven项目需加入如下依赖: <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi</artifactId> <version>3.10-FINAL</version> </dependency> <dependency> <gr

  • Java语言实现二叉堆的打印代码分享

    Java语言实现二叉堆的打印代码分享

    二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树).二叉堆有两种:最大堆和最小堆.最大堆:父结点的键值总是大于或等于任何一个子节点的键值:最小堆:父结点的键值总是小于或等于任何一个子节点的键值. 打印二叉堆:利用层级关系 我这里是先将堆排序,然后在sort里执行了打印堆的方法printAsTree() public class MaxHeap<T extends Comparable<? super T>> { private T[] data; pr

  • java IO流读取图片供前台显示代码分享

    java IO流读取图片供前台显示代码分享

    最近项目中需要用到IO流来读取图片以提供前台页面展示,由于以前一直是用url路径的方式进行图片展示,一听说要项目要用IO流读取图片感觉好复杂一样,但任务下达下来了,做为程序员只有选择去执行喽,于是找了点资料看了会api, 嘿感觉挺简单的,由于是第一次采用IO流的方式进行读取图片供页面显示,所以把以下代码记录一下 后台代码: /** * IO流读取图片 by:long * @return */ @RequestMapping(value = "/IoReadImage/{imgName}"

随机推荐