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

相关文章

来自专栏技术沉淀

Ruby练习一=> {'a' => 3, 'man' => 1, 'canal' => 1, 'panama' => 1, 'plan' => 1}returns the list ["Pam", "

952
来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

1022
来自专栏成长道路

org.apache.spark.sql.AnalysisException: Table or view not found: `traintext`.`train`; line 1 pos 14;

恭喜老铁,跟我遇到了一样的问题,接下来是解决方法: 遇到的问题: org.apache.spark.sql.AnalysisException: Table o...

9380
来自专栏10km的专栏

SSD(Single Shot MultiBox Detector):create_list.sh io.cpp:187 Could not open or find file

今天在为SSD训练自己的数据时执行caff/data/VOC0712/create_list.sh时报了好多这个错误: E0412 16:28:31.6534...

2738
来自专栏python3

openvpn linux客户端使用

内网服务器是linux的,需要连接openvpn,访问线上的应用服务。需要安装客户端,方法和服务器类似。

1112
来自专栏一个会写诗的程序员的博客

13.12 Spring Boot集成Security中遇到的问题13.12 Spring Boot集成Security中遇到的问题问题1:Spring Boot集成Security使用数据库用户角色

sql语法手误。1?这地方写错了,应该是?1。这在敲代码的时候,手速一旦稍有不慎,就会导致前后顺序颠倒,而导致输入错误。这个虽然说是“低级错误”,但是错误搞起来...

812
来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1764
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2691
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2332
来自专栏智能计算时代

Best Bluemix Content

image.png Watson Services for Bluemix Sample Apps: Watson Films App (Video) Wats...

2624

扫码关注云+社区