题目描述： 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路： 1.用两个指针分别指向链表的第一个结点，比较这两个结点的大小 2.将小的结点加入到合并后的链表中，并向后移动当前指针 3.两个链表中，若有一个链表先扫描完，就将对应的另一个链表的剩余部分直接添加到合并后的链表中。
实现： 递归法：
public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } if(list1.val <= list2.val){ list1.next = Merge(list1.next, list2); return list1; } else{ list2.next = Merge(list1, list2.next); return list2; } }非递归：
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null && list2 == null) return null; if(list1 == null) //链表1为空，则直接返回链表2 return list2; if(list2 == null) //链表2为空，则直接返回链表1 return list1; ListNode head = new ListNode(-1); ListNode list = head; while(list1 != null && list2 != null) { if(list1.val > list2.val) { list.next = list2; list = list.next; list2 = list2.next; } else { list.next = list1; list = list.next; list1 = list1.next; } } //若两链表长度不相等，此时链表1或链表2已完成插入，直接将剩余部分接上 while(list1 != null) { list.next = list1; list = list.next; list1 = list1.next; } while(list2 != null) { list.next = list2; list = list.next; list2 = list2.next; } return head.next; } }