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

相关文章

来自专栏10km的专栏

java:利用fastjson判断一个类型(java.lang.reflect.Type)是否是一个javabean

fastjson中JSON.toJSON(Object javaObject)方法将一个java对象被序列化成json对象时,返回的对象类型有三种可能:JSON...

2168
来自专栏程序生活

Leetcode-Easy 572. Subtree of Another Tree

572. Subtree of Another Tree 描述: 给定两个二叉树s和t,判断t是否s的一个子树。要求结构完全一致 ? ? 思...

2894
来自专栏mathor

LeetCode138. 复制带随机指针的链表

 第一步:复制结点,复制的结点放在待复制的结点后,依然组成一个单链表  第二步:串接随机指针  第三步:将原单链表与复制链表拆开

502
来自专栏文武兼修ing——机器学习与IC设计

二叉查找树二叉查找树

二叉查找树 二叉查找树是一种特殊的二叉树,该数据结构的核心性质是: 对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值,而它的右子树中所有关键字值...

27911
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之重建二叉树(九度OJ1385)

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

1785
来自专栏佳爷的后花媛

jQuery

jquery 语法是为HTML元素的选取编制的,可以对元素执行某些操作。 基础语法就是:$(selector).action()

893
来自专栏赵俊的Java专栏

落单的数Ⅲ

1165
来自专栏武培轩的专栏

剑指Offer-二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 思路一: 由于要求链表是有序...

2563
来自专栏技术博文

js实现php中sleep()延时的功能

1. jquery的$.delay()方法 设置一个延时来推迟执行队列中之后的项目。这个方法不能取代JS原生的setTimeout。 The .delay() ...

3338
来自专栏武培轩的专栏

剑指Offer-把数组排成最小的数

题目描述 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成...

2675

扫描关注云+社区