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.

经典的链表基本操作。维护两个指针对应两个链表.

方法一：

因为一般会以一条链表为基准，比如说l1, 那么如果l1当期那的元素比较小，那么直接移动l1即可，否则将l2当前的元素插入到l1当前元素的前面。算法时间复杂度是O(m+n),m和n分别是两条链表的长度，空间复杂度是O(1)

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {14         if (l1 == null) return l2;15         if (l2 == null) return l1;16         ListNode dummy = new ListNode(-1);17         dummy.next = l1;18         ListNode cur = dummy;19         while (l1 != null && l2 != null) {20             if (l1.val < l2.val) {21                 l1 = l1.next;22             }23             else {24                 ListNode next = l2.next;25                 l2.next = cur.next;26                 cur.next = l2;27                 l2 = next;28             }29             cur = cur.next;30         }31         if (l2 != null) {32             cur.next = l2;33         }34         return dummy.next;35     }36 }

方法二（推荐方法1）： 

新的Linkedlist不以任何现有List为依托，维护一个dummmy node和当前节点ListNode cur，把两个list的元素往里面插入作为cur.next，每次不new一个新的ListNode, 而是用已有的。相较于法一最后需要讨论两个list各自没有走完的情况

1 public class Solution { 2     public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 3         if (l1 == null) return l2; 4         if (l2 == null) return l1; 5         ListNode dummy = new ListNode(-1); 6         ListNode cur = dummy; 7         while (l1 != null && l2 != null) { 8             if (l1.val < l2.val) { 9                 cur.next = l1;10                 l1 = l1.next;11             }12             else {13                 cur.next = l2;14                 l2 = l2.next;15             }16             cur = cur.next;17         }18         if (l1 != null) {19             cur.next = l1;20         }21         else if (l2 != null) {22             cur.next = l2;23         }24         return dummy.next;25     }26 }

方法三：（推荐方法2）Recursion

1 public ListNode mergeTwoLists(ListNode l1, ListNode l2){ 2         if(l1 == null) return l2; 3         if(l2 == null) return l1; 4         if(l1.val < l2.val){ 5             l1.next = mergeTwoLists(l1.next, l2); 6             return l1; 7         } else{ 8             l2.next = mergeTwoLists(l1, l2.next); 9             return l2;10         }11 }