剑指 offer代码解析——面试题26复杂链表的复制

本题详细解析均在代码注释中:

/**
 * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个结点。
 * @author 大闲人柴毛毛
 * @date 2016年3月16日
 */
public class CopyLink {
	/**
	 * 分析:复制单链表较为简单,只需遍历单链表,创建结点,同时将前后连个结点相继连起来即可。
	 * 本题的难点在于:每个结点还有一个sibling域,指向链表的任意一个结点。
	 * 本题最直观的思路有两种:
	 * 1.先复制单链表,然后再复制sibling域;
	 * 2.在复制单链表的同时确定sibling域名。
	 * 第一种方法较为简单,复制完单链表后需再次遍历原链表,
	 * 若当前结点的sibling域不为空,则从当前结点开始依次向后查找sibling域指向的位置,
	 * 我们可以用一个计数器count记录当前结点与sibling域指向的结点直接的距离,
	 * 然后在新链表中,以该结点为起点,向后走count步即为sibling域指向的结点。
	 * 这种方式由于每个结点都要依次向后查找sibling指向的结点,因此时间复杂度为O(n^2)。
	 */
	
	/**
	 * 下面介绍一种巧妙的方法:
	 * 首先复制每个结点,并将他们插入在原结点的后面,从而形成一条新的链表;
	 * 然后遍历链表,若当前结点a的sibling不为空,则将a的下一个结点b的sibling指向a.sibling的下一个结点;
	 * 最后拆分链表:将奇数位连起来,偶数位连起来即可。
	 * 代码如下:
	 */
	
	/**
	 * 复制复杂链表
	 * @param first 复杂链表的头结点
	 * @return 返回复制后的复杂链表
	 */
	static boolean result = true;//copyLink执行结果
	public static <T> Node<T> copyLink(Node<T> first){
		//若链表为空
		if(first==null){
			System.out.println("链表为空!");
			result = false;
			return null;
		}
		
		//复制每个结点,并插入原结点之后
		Node<T> p = first;
		while(p!=null){
			//创建新结点
			Node<T> node = new Node<T>();
			node.data = p.data;
			//将新结点插入p之后
			node.next = p.next;
			p.next = node;
		}
		
		//复制每个结点的sibling域
		p = first;
		while(p!=null){
			p.next.sibling = p.sibling.next;
		}
		
		//拆分链表
		p = first;
		Node<T> q = p.next;
		Node<T> first_copy = q;//被复制链表的头结点
		while(q!=null){
			p.next = q.next;
			p = q;
			q = q.next;
		}
		
		return first_copy;
	}
	
	
	/**
	 * 综上所述:上述方法只需扫描链表3次:
	 * 1.第一遍复制每个结点,并依次插入结点的后面;
	 * 2.第二遍复制每个结点的sibling域;
	 * 3.第三次拆分链表。
	 * 因此,上述方式的时间复杂度为O(n)
	 */
}



/**
 * 复杂链表的一个结点
 */
class Node<T>{
	T data;
	Node<T> next;
	Node<T> sibling;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python爬虫基础知识:Python中的正则表达式教程

云豆贴心提醒,本文阅读时间7分钟 正则表达式在Python爬虫中的作用就像是老师点名时用的花名册一样,是必不可少的神兵利器。 一、 正则表达式基础 1.1.概...

2466
来自专栏自然语言处理

Python读书笔记:需要注意的70个小问题

4 单双引号括起来的,字符串可以包含引号和撇号。用法:"this's a cup"

1032
来自专栏Linux驱动

快速排序(详解)

描述: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序...

1829
来自专栏决胜机器学习

有趣的算法(五) ——Dijkstra双栈四则运算

有趣的算法(五)——Dijkstra双栈四则运算 (原创内容,转载请注明来源,谢谢) 一、概念 近期看到算法书上,提到dijkstra双栈的方法,实现输入一...

4707
来自专栏余林丰

5.比较排序之归并排序(非递归)

  在上一节中讲解了归并排序的递归版《4.比较排序之归并排序(递归)》,通常来讲,递归版的归并排序要更为常用,本节简单介绍下非递归版的归并排序。思路和递归版相...

1999
来自专栏强仔仔

Java基础知识-基本数据类型相互转型

这是我第一次系统性的总结java这门语言的基础知识用法,因本人经验有限,所以在总结的过程中如果有错误或者有歧义等等之类的问题,都可以联系我QQ:20801753...

1888
来自专栏浪淘沙

java学习day08 集合

2.集合 数组:使用索引值存数组,利用数组的特点来操作数据,遍历。 数组中可以存储基本数据类型,集合只能存储对象。

1064
来自专栏从流域到海域

《Java程序设计基础》 第5章手记

《Java程序设计基础》 第5章手记 - 一维和多维数组的定义 - 数组元素的访问 - 字符串及其应用 这节课给大家发福利,将会在后面贴实验...

1727
来自专栏CDA数据分析师

Python面试中8个必考问题

1、下面这段代码的输出结果是什么?请解释。 ? 怎样修改extendList的定义能够产生以下预期的行为? 上面代码输出结果将是: ? 很多人都会误认为list...

18010
来自专栏编程坑太多

数据结构与算法—选择排序(Java实现)

1436

扫码关注云+社区