题目：
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.
分析：合并两个有序序列，这个归并排序中的一个关键步骤。这里是要合并两个有序的单链表。由于链表的特殊性，在合并时只需要常量的空间复杂度。
编码：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) return null; if(l1 == null && l2 != null) return l2; if(l2 == null && l1 != null) return l1; ListNode p = l1; ListNode q = l2; ListNode newHead = new ListNode(-1);//定义头结点 ListNode r = newHead; while(p != null && q != null){ if(p.val < q.val){ r.next = p; //这里，将待排序节点直接拼接在新节点后，而不用再创建新节点。节省了空间复杂度。 p = p.next; r = r.next; } else { r.next = q; q = q.next; r = r.next; } } if(p != null) r.next = p; if(q != null) r.next = q; return newHead.next; }
21. Merge Two Sorted Lists (Java 合并有序链表 空间复杂度O(1))
原文：http://www.cnblogs.com/mydesky2012/p/5768704.html