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

相关文章

来自专栏机器学习从入门到成神

Java之使用增强for循环和迭代器遍历

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1431
来自专栏小筱月

java map遍历、排序,根据value获取key

若要取 map 中 value 的最大值 或 与之对应的 key(整型或浮点型):可利用list

3382
来自专栏老马说编程

(38) 剖析ArrayList / 计算机程序的思维逻辑

从本节开始,我们探讨Java中的容器类,所谓容器,顾名思义就是容纳其他数据的,计算机课程中有一门课叫数据结构,可以粗略对应于Java中的容器类,我们不会介绍所有...

2115
来自专栏一英里广度一英寸深度的学习

二叉树添加删除节点Python

采用递归调用实现二叉树添加、删除节点。文章采用Python对象引用方式实现指针结构的创建。

2902
来自专栏IT可乐

JDK1.8源码(十)——java.util.LinkedHashSet类

  同 HashSet 与 HashMap 的关系一样,本篇博客所介绍的 LinkedHashSet 和 LinkedHashMap 也是一致的。在 JDK 集...

721
来自专栏武培轩的专栏

剑指Offer-第一个只出现一次的字符位置

题目描述 在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置 思路 思路一: 使用整型数组对出现次数进行...

3829
来自专栏陈树义

3.Java集合总结系列:Set接口及其实现

一、Set接口 Set 接口与 List 接口相比没有那么多操作方法,比如: 1、List 接口能直接设置或获取某个元素的值,而Set接口不能。 2、List ...

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

逆序数(二叉查找树)

已知数组nums,求新数组count,count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。 例如: nums = [5,2,6,1],...

653
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-18(02)总结Map,HashMap,HashMap与Hashtable区别,Collections工具类

(8)Hashtable和HashMap的区别? package cn.itcast_07; import java.util.Hashtable; /* *...

2895
来自专栏黑泽君的专栏

TreeSet存储元素自然排序和唯一的代码及图解

821

扫码关注云+社区