文档章节

面试题

许雷神
 许雷神
发布于 2015/05/15 13:22
字数 678
阅读 16
收藏 0
import java.util.Random;

/**
 * 面试题:这是一个链表题,链表不光有next域还有一个指向任意链上任意一个结点的随机域random,
 * 注意random可以指向null,请完成对一个链表的复制。
 * 
 * 解答: 如果没有随机域random,这个题目就很简单,扫描一遍构建新结点即可,现在的难处在于复制 链表中random
 * 指向的结点可能还没创建,所以需要先创建所有结点并复制数据域,这一步只需 遍历一遍即可,然后再处理链接域
 * 方法1:	1、创建新结点newNode并复制数据域
 * 			2、保存oldList的链接状态
 * 			3、将oldList的oldNode结点next域指向对应的newNode
 * 			4、newNode.random = old.random.next
 * 			5、利用2保存的状态恢复oldList的next域
 * 方法1中第二2步需要一个O(n)的辅助空间。
 * 
 * 方法2:	1、在oldNode[i]与oldNode[i+1]插入newNode[i],最后一个结点直接放在末尾
 * 			2、newNode.random = newNode.random.next建立复制链表的随机域
 * 			3、恢复两个链表的next域
 * 
 * @author jiqunpeng email jiqunpeng@gmail.com
 * 
 *  
 */
public class RandomLink {
	public RandomLink next = null;
	public RandomLink random = null;
	public long id = Long.MIN_VALUE;
	private static Random rand = new Random(47);

	/**
	 * 构造一个长度为n的链表
	 * 
	 * @param n
	 * @return
	 */
	public static RandomLink generator(int n) {
		RandomLink[] list = new RandomLink[n];
		for (int i = 0; i < n; i++) {
			list[i] = new RandomLink();
			list[i].id = i;
		}
		for (int i = 0; i < n; i++) {
			if (i == n - 1)// 最后一个结点next域为null
				list[i].next = null;
			else
				list[i].next = list[i + 1];
			int r = rand.nextInt(n + 1);
			if (r == n)
				list[i].random = null;
			else
				list[i].random = list[r];
		}
		return list[0];// 返回头结点
	}
	/**
	 * 按方法2复制链表
	 * @param oldList
	 * @return
	 */
	public static RandomLink copy(RandomLink oldList) {
		// 将新的结点插入到两个结点之间
		RandomLink oldNode = oldList;
		while (oldNode.next != null) {
			RandomLink newNode = new RandomLink();
			newNode.id = oldNode.id;
			newNode.next = oldNode.next;
			oldNode.next = newNode;
			oldNode = newNode.next;
		}
		// 最后一个新结点插入到末尾即可
		RandomLink lastNode = new RandomLink();
		lastNode.id = oldNode.id;
		lastNode.next = null;
		oldNode.next = lastNode;
		// 构造新链表的随机链域
		oldNode = oldList;
		RandomLink copyNode = oldList.next;
		RandomLink newNode;
		while (oldNode != null) {
			newNode = oldNode.next;
			// 复制新结点的随机链域
			if (oldNode.random == null)
				newNode.random = null;
			else
				newNode.random = oldNode.random.next;
			oldNode = oldNode.next.next;
		}
		// 恢复结点的next域
		oldNode = oldList;
		newNode = oldNode.next;
		while (true) {
			oldNode.next = newNode.next;// 重新链接旧结点的next
			oldNode = oldNode.next;// 下一个旧结点
			if (oldNode == null)
				break;
			newNode.next = oldNode.next;// 重新链接新结点的next
			newNode = newNode.next;// 下一个新结点
		}
		return copyNode;
	}

	public String getString() {
		return super.toString().split("@")[1];
	}

	@Override
	public String toString() {
		String nextId;
		if (next == null)
			nextId = "null";
		else
			nextId = Long.valueOf(next.id).toString() + "@" + next.getString();//
		String rId;
		if (random == null)
			rId = "null";
		else
			rId = Long.valueOf(random.id).toString() + "@" + random.getString();//
		return super.toString() + "\t" + id + "\t" + nextId + "\t" + rId;
	}

	public static void printList(RandomLink list) {
		RandomLink node = list;
		while (node != null) {
			System.out.println(node);
			node = node.next;
		}
	}

	public static void main(String[] args) {
		RandomLink list = RandomLink.generator(5);
		System.out.println("原始链表:");
		RandomLink.printList(list);
		RandomLink copyList = RandomLink.copy(list);
		System.out.println("复制后的原始链表:");
		RandomLink.printList(list);
		System.out.println("复制后的链表:");
		RandomLink.printList(copyList);
	}
}


本文转载自:#

共有 人打赏支持
许雷神
粉丝 7
博文 13
码字总数 0
作品 0
广州
私信 提问
最新iOS面试必看题视频教程(附大神简历要素)

本文是由尚学堂iOS学院总结的ios开发者在求职时会遇到的一些面试题 ,并通过实际代码演练将课程详尽的讲解出来,希望对学习ios或从事ios开发行业的朋友有所帮助。 001尚学堂iOS面试题命名规范...

2846613430
2016/04/12
388
0
2017派卧底去阿里、京东、美团、滴滴带回来的面试题及答案

最近有很多朋友去目前主流的大型互联网公司面试(阿里巴巴、京东、美团、滴滴),面试回来之后会发给我一些面试题。有些朋友轻松过关,拿到offer,但是有一些是来询问我答案的。 我特意整理了...

youanyyou
2017/11/08
0
0
Android开发工程师面试指南(面试题集附答案、简历模板)

给Android开发工程师的一份面试指南,包含面试题集与简历模板。 面试题集 面试题集里的答案大部分来源于我的博客,因此这个题集也相当于是我的博客的精华版,希望对需要面试的Android同学有所...

郭孝星
2018/04/08
0
0
Linux运维MySQL必会面试题100道

老男孩教育Linux运维班MySQL必会面试题100道 (1)基础笔试命令考察 (要求:每两个同学一组,一个口头考,一个上机实战作答,每5个题为一组,完成后换位) 1.开启MySQL服务 2.检测端口是否运...

老男孩oldboy
2017/08/25
0
0
金九银十,史上最强 Java 面试题整理。

以下会重新整理所有 Java 系列面试题答案、及各大互联网公司的面试经验,会从以下几个方面汇总,本文会长期更新。 Java 面试篇 史上最全 Java 面试题,带全部答案 史上最全 69 道 Spring 面试...

Java技术栈
2018/09/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
0
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
0
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
0
0
XML

学习目标  能够说出XML的作用  能够编写XML文档声明  能够编写符合语法的XML  能够通过DTD约束编写XML文档  能够通过Schema约束编写XML文档  能够通过Dom4j解析XML文档 第1章 xm...

stars永恒
昨天
0
0
RabbitMQ学习(2)

1. 生产者客户端 void basicPublish(String exchange, String routingKey, boolean mandatory, boolean immediate, BasicProperties props, byte[] body) 1. 在生产者客户端发送消息时,首先......

江左煤郎
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部