剑指 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 条评论
登录 后参与评论

相关文章

来自专栏博岩Java大讲堂

Java集合--List

3627
来自专栏芋道源码1024

Jedis 对 Redis 的操作详解

本篇主要阐述Jedis对redis的五大类型的操作:字符串、列表、散列、集合、有序集合。

1193
来自专栏木子昭的博客

Python实现深度优先与广度优先

二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归 ? 二叉树 深度优先 先序遍历(父, 左子, 右子) 0,...

6287
来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

39011
来自专栏机器学习入门

LWC 52:687. Longest Univalue Path

LWC 52:687. Longest Univalue Path 传送门:687. Longest Univalue Path Problem: Given...

2277
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

2009
来自专栏与神兽党一起成长

说一说java.util.Arrays.ArrayList

java.util.Arrays.ArrayList(下文:Arrays.ArrayList)是java.util.Arrays的私有静态内部类,他实现的接口,...

1013
来自专栏吾爱乐享

JAVA之学习SimpleDateFormat类的概述和方法案例

1135
来自专栏吾爱乐享

java之学习集合带All的方法的案例分析

1093
来自专栏ios 技术积累

swift set

set是一个Set类型的集合,集合中只能出现String类型的数据,如果放入了其他类型,会报错。但是如果没有指定集合中的数据类型,那就没有关系。

821

扫码关注云+社区