题目：
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;
}