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

相关文章

来自专栏大闲人柴毛毛

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

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

35410
来自专栏用户2442861的专栏

C++的函数隐藏、覆盖和重载

http://blog.csdn.net/lin49940/article/details/5553664

751
来自专栏mathor

1小时精通c++面向对象编程

重载二元运算符,只显式说明一个参数;该参数为操作数的右操作数,左操作数由this指针(指向调用该成员函数的对象)提供

713
来自专栏AILearning

反射的应用与理解

反射就是把Java类中的各种成分映射成相应的java类 <代理模式会用到反射,SSH框架会用到框架> 反射使用用中用到的是:字节码(获取类的字节码的三种方式) ...

1926
来自专栏大闲人柴毛毛

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

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

2584
来自专栏Zephery

redis

redis的数据结构 数据结构类型 结构存储的值 结构的读写能力 STRING 可以是字符串、整数、或者浮点数 对整个字符串或者字符串的其中一部分...

5579
来自专栏漫漫深度学习路

python class 一点总结

Python class 总结 细数class中的 __**__ __init__(self, *values) 对象的初始化函数,初始化类的实例时,会调用...

1628
来自专栏书山有路勤为径

堆的基础知识

二叉堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。最大堆,树种各个父 节点的值总是大于或等于任何一个子节点的值;最小堆,树种各个父节点的值总是小于或 等...

673
来自专栏章鱼的慢慢技术路

数据结构与算法笔试面试题整理

b.对每一对相邻的元素做同样的工作,从开始的第一对一致到结尾的最后一对,经过这一步,最后的元素将是最大值;

993
来自专栏郭耀华‘s Blog

剑指offer第三天

21.栈的压入、弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,...

2716

扫码关注云+社区