问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

链表1和链表2都是递增排序的，链表3为链表1和2合并后的链表

图（a）：比较两个头结点的值，链表1的头结点为1 < 链表2的头结点为2，所以链表1的头结点时合并后链表的头结点。
图（b）：合并剩余的，同前面步骤，比较两个头结点的值，链表2的头结点为2 < 链表1的头结点为3，所以链表2的头结点时合并后链表的头结点。这个结点和前面合并链表时得到的链表的尾结点（值为1的结点）链接起来。
当得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，合并的步骤和之前的是一样的。可以看出是递归解决的。

**需要注意的是:**空指针问题
输入的是空链表，就会出现空指针，所以需要对空链表单独处理
当第一个链表为空（即头结点为空指针），和第二个链表合并，结果是第二个链表
当第二个链表为空（即头结点为空指针），和第一个链表合并，结果是第一个链表
两个链表都为空，结果是空链表。

java实现

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1, ListNode list2) {if (list1 == null && list2 == null)return null;//两个链表都为空，结果是空链表else if (list1 == null)return list2;//当第一个链表为空，和第二个链表合并，结果是第二个链表else if (list2 == null)return list1;//当第二个链表为空（即头结点为空指针），和第一个链表合并，结果是第一个链表ListNode head = null;//链表1的头结点 < 链表2的头结点，所以链表1的头结点时合并后链表的头结点,反之，同理if (list1.val < list2.val) {head = list1;head.next = Merge(list1.next, list2);} else {head = list2;head.next = Merge(list1, list2.next);}return head;}
}