剑指offer代码解析——面试题17合并两个排序的链表

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

/**
 * 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
 * @author 大闲人柴毛毛
 * @date 2016年3月14日
 */
public class MergeLink {
	/**
	 * 分析:我们把两个单链表分为a1、a2,每次从a2中取出头结点,然后在a1中寻找插入点插入,重复上述操作直到a2中结点被取光为止。
	 * 代码如下:
	 */
	
	/**
	 * 合并两个递增的单链表
	 * @param first1 第一个链表的头结点
	 * @param first2 第二个链表的头结点
	 * @return 返回合并后链表的头结点
	 */
	public static Node<Integer> mergeLink(Node<Integer> first1, Node<Integer> first2){
		//若a1为空,a2为空
		if(first1==null && first2==null){
			System.out.println("两个链表均为空!");
			return null;
		}
		
		//若a1为空,a2不为空,则返回a2
		if(first1==null && first2!=null)
			return first2;
		
		//若a2为空,a1不为空,则返回a1
		if(first1!=null && first2==null)
			return first1;
		
		//若a1、a2均不为空,则进行合并
		while(first2!=null){
			//p指向链表一中的当前结点
			Node<Integer> p = first1;
			
			//若first2<p,则将first2插入到p之前
			if(first2.data < p.data){
				//q指向first2
				Node<Integer> q = first2;
				//first2指向后继结点
				first2 = first2.next;
				//将a2的头结点摘下来,装到a1的头上
				q.next = p;
				first1 = q;
			}
			
			//若first2>=p时,p一直向后找,直到找到first2<p时停止,将first2插入到p的前面
			Node<Integer> p_pre = p;//p_pre指向p的前一个结点
			while(p.data<=first2.data && p!=null){
				p_pre = p;
				p = p.next;
			}
			//q指向first2
			Node<Integer> q = first2;
			//first2指向后继结点
			first2 = first2.next;
			//q的后继结点设为p
			q.next = p;
			//p_pre的后继结点设为q
			p_pre.next = q;
		}
		
		return first1;
	}
}


/**
 * 定义结点 
 */
class Node<T>{
	public T data;
	public Node<T> next;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

712
来自专栏大数据和云计算技术

算法基础6:二叉树查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第6篇《二叉树查找》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基...

3275
来自专栏数据结构与算法

2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

3086
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

773
来自专栏大闲人柴毛毛

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

本题详细解析均在代码注释中: /** * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个...

2514
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题16反转单链表

本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class...

34810
来自专栏程序生活

数据结构-顺序表的定义及python实现

1 顺序表的定义 线性表 是具有相同数据类型的n个数据元素的有限序列。 顺序表 使用组地址连续的存储单元、依次存储线性表中的数据元素,从而使得逻辑上相邻的两...

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

树与二叉表达树树基础二叉表达树

树基础 定义 数的定义 可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一...

2646
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

1857
来自专栏有趣的Python

6-玩转数据结构-二分搜索树

电脑中的文件夹就是一种树结构,计算机中让人们使用的存储结构来源于生活。图书馆分区,分类,分子类。

902

扫描关注云+社区