文档章节

面试题

许雷神
 许雷神
发布于 2015/05/15 13:22
字数 678
阅读 15
收藏 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
Linux运维MySQL必会面试题100道

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

老男孩oldboy
2017/08/25
0
0
2017派卧底去阿里、京东、美团、滴滴带回来的面试题及答案

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

youanyyou
2017/11/08
0
0
金九银十,史上最强 Java 面试题整理。

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

Java技术栈
09/13
0
0
2018 前端面试准备

前端面试常见问题按知识点分类整理 前端面试常考问题整理,按模块知识点分类,持续完善中... Front-end-Developer-Questions by Modules and knowledge 前端面试经典问题:CSS 中居中的几种方...

掘金官方
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker部署springboot项目

安装docker 菜鸟教程 springboot项目 maven依赖 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001......

yimingkeji
今天
10
0
ios多个target

1.建立3个target,分别为heroone,heroone test,heroone dev;分别为正式环境,test环境,dev环境 2.注意取消掉autocreate以防止名字不对,分别以Duplicate的方式建立另外两个scheme 3.创建...

HeroHY
今天
5
0
php获取客户端IP

php获取客户端IP 首先先阅读关于IP真实性安全的文章:如何正確的取得使用者 IP? 「任何從客戶端取得的資料都是不可信任的!」 HTTP_CLIENT_IP头是有的,但未成标准,不一定服务器都实现。 ...

DrChenXX
昨天
0
0
. The valid characters are defined in RFC 7230 and RFC 问题

通过这里的回答,我们可以知道: Tomcat在 7.0.73, 8.0.39, 8.5.7 版本后,添加了对于http头的验证。 具体来说,就是添加了些规则去限制HTTP头的规范性 参考这里 具体来说: org.apache.tom...

west_coast
昨天
1
0
刷leetcode第704题-二分查找

今天双十一买的算法书到货了,路上刷到有人说的这个题,借(chao)鉴(xi)一下别人的思路,这个是C++标准库里面的经典方法,思路精巧,优雅好品味 int search(int* nums, int numsSize, in...

锟斤拷烫烫烫
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部