Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
--合并两个有序链表，合并之后仍有序
这道混合插入有序链表和我之前那篇混合插入有序数组非常的相似，仅仅是数据结构由数组换成了链表而已，代码写起来反而更简洁。具体思想就是新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。
代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //在头部定义一个没有意义的节点，可以省去之后的许多if判断 ListNode la = new ListNode(-1), lm = la; // if(l1==null || l2 == null){ // return (l1!=null)?l1:l2; // } // ListNode la = null,lm=null; while(l1!=null && l2!=null){ // if(la == null){ // if(l1.val<=l2.val){ // la = lm = l1; // l1 = l1.next; // } // else{ // la = lm = l2; // l2 = l2.next; // } // continue; // } if(l1.val<=l2.val){ lm.next = l1; lm = l1; l1= l1.next; } else{ lm.next = l2; lm = l2; l2=l2.next; } } lm.next = (l1!=null)?l1:l2; return la.next; }} 下面我们来看递归的写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果l1的小，那么对于l1的下一个节点和l2调用递归函数，将返回值赋值给l1.next，然后返回l1；否则就对于l2的下一个节点和l1调用递归函数，将返回值赋值给l2.next，然后返回l2。
代码如下：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null || l2 == null){ return (l1!=null)?l1:l2; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l2.next, l1); return l2; } }}