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 }
[leetcode]Merge Two Sorted Lists,布布扣,bubuko.com
[leetcode]Merge Two Sorted Lists
原文：http://www.cnblogs.com/huntfor/p/3855352.html