剑指Offer面试题：19.合并两个排序的链表
一、题目
————————————————
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
————————————————
二、思路
————————————————
递归实现：合并过程中，每次都是从两个链表中找出较小的一个来链接，因此可以采用递归来实现：当任意一个链表为null时，直接链接另一个链表即可；其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
非递归实现：非递归实现比较容易想到，直接进行分情况讨论即可，要稍微注意下后面代码中头结点的赋值过程。
————————————————
三、解决问题
————————————————
测试算例
1.功能测试（两个链表有多个或一个结点；结点值相同、不同）
2.特殊测试（任意一个或者两个链表的头结点为null）
————————————————
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-24 10:29
*/
/**
* 输入两个单调递增的链表，输出两个链表合成后的链表，
* 当然我们需要合成后的链表满足单调不减规则。
*/
public class Solution19 {
public static void main(String[] args) {
Solution19 demo = new Solution19();
System.out.println("==============================");
System.out.println("递归test1");
demo.test1();
System.out.println("==============================");
System.out.println("递归test2");
demo.test2();
System.out.println("==============================");
System.out.println("递归test3");
demo.test3();
System.out.println("==============================");
System.out.println("非递归test4");
demo.test4();
System.out.println("==============================");
System.out.println("非递归test5");
demo.test5();
System.out.println("==============================");
System.out.println("非递归test6");
demo.test6();
System.out.println("==============================");
}
/*
* 递归版本
* 递归实现：
* 合并过程中，每次都是从两个链表中找出较小的一个来链接，因此可以采用递归来实现：
* 当任意一个链表为null时，直接链接另一个链表即可；
* 其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
*/
public ListNode Merge01(ListNode list1,ListNode list2) {
//当任意一个链表为null时，直接链接另一个链表即可；
if(null == list1){
return list2;
}
if(null == list2){
return list1;
}
//其余情况只需要在两个链表中找出较小的一个结点进行链接，该结点的next值继续通过递归函数来链接。
if(list1.val < list2.val){
list1.next = Merge01(list1.next,list2);//
return list1;
}else{
list2.next = Merge01(list1, list2.next);
return list2;
}
}
/*
* 非递归版本
* 非递归实现：非递归实现比较容易想到，直接进行分情况讨论即可，
* 要稍微注意下后面代码中头结点的赋值过程。
*/
public ListNode Merge02(ListNode list1,ListNode list2) {
//当任意一个链表为null时，直接链接另一个链表即可；
if(null == list1){
return list2;
}
if(null == list2){
return list1;
}
ListNode dummyHead = new ListNode(0);//不能为null
ListNode temp = dummyHead;
while(list1 != null && list2 != null) {
if (list1.val < list2.val) {
temp.next = list1;
list1 = list1.next;
} else {
temp.next = list2;
list2 = list2.next;
}
temp = temp.next;
}
if(null == list1){
temp.next = list2;
}else{
temp.next = list1;
}
return dummyHead.next;
}
//=====================测试代码=======================
/*
* 1.功能测试（两个链表的头结点为null）
*/
void test1() {
//1个递增排序的链表
ListNode list1 = null;
//1个递增排序的链表
ListNode list2 = null;
ListNode head = Merge01(list1, list2);
if (null == head){
System.out.println("链表为null");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
}
/*
* 2.两个链表有多个结点
*/
void test2() {
ListNode list1 = new ListNode(1);
ListNode node1 = new ListNode(3);
ListNode node2 = new ListNode(5);
ListNode list2 = new ListNode(2);
ListNode node3 = new ListNode(4);
ListNode node4 = new ListNode(6);
//1个递增排序的链表
list1.next = node1;
node1.next = node2;
//1个递增排序的链表
list2.next = node3;
node3.next = node4;
ListNode head = Merge01(list1,list2);
if (null == head){
System.out.println("");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
System.out.println();
}
/*
* 3.两个链表中一个为null,另一个有多个结点
*/
void test3() {
ListNode list1 = new ListNode(1);
ListNode node1 = new ListNode(3);
ListNode node2 = new ListNode(5);
ListNode list2 = null;
//1个递增排序的链表
list1.next = node1;
node1.next = node2;
ListNode head = Merge01(list1,list2);
if (null == head){
System.out.println("");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
System.out.println();
}
//=====================测试代码=======================
/*
* 1.功能测试（两个链表的头结点为null）
*/
void test4() {
//1个递增排序的链表
ListNode list1 = null;
//1个递增排序的链表
ListNode list2 = null;
ListNode head = Merge02(list1, list2);
if (null == head){
System.out.println("链表为null");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
}
/*
* 2.两个链表有多个结点
*/
void test5() {
ListNode list1 = new ListNode(1);
ListNode node1 = new ListNode(3);
ListNode node2 = new ListNode(5);
ListNode list2 = new ListNode(2);
ListNode node3 = new ListNode(4);
ListNode node4 = new ListNode(6);
//1个递增排序的链表
list1.next = node1;
node1.next = node2;
//1个递增排序的链表
list2.next = node3;
node3.next = node4;
ListNode head = Merge02(list1,list2);
if (null == head){
System.out.println("");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
System.out.println();
}
/*
* 3.两个链表中一个为null,另一个有多个结点
*/
void test6() {
ListNode list1 = new ListNode(1);
ListNode node1 = new ListNode(3);
ListNode node2 = new ListNode(5);
ListNode list2 = null;
//1个递增排序的链表
list1.next = node1;
node1.next = node2;
ListNode head = Merge02(list1,list2);
if (null == head){
System.out.println("");
}else{
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
System.out.println();
}
}
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
Java基础 文章被收录于专栏
建立本人的Java基础技术栈积累库
