[leetcode]Merge Two Sorted Lists

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为基准，拿l2的点逐个插入到l1中，两个链表都是一次遍历，我这里没有做优化，时间复杂度O(m+n)，空间复杂度O(1)

 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 head = new ListNode(1);
 6         head.next = l1;
 7         ListNode pre = head;
 8         ListNode node = l2;
 9         while(l2 != null){
10             node = l2;
11             while(pre.next != null && pre.next.val <= node.val){
12                 pre = pre.next;
13             }
14             l2 = node.next;
15             node.next = pre.next;
16             pre.next = node;
17             pre = node;//如果这句删掉的话，相当于l2扫描了两边，l1扫描一遍，但是时间复杂度不变
18         }
19         return head.next;
20     }
21 }