本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/41750865
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.
For example,
Given 1->2->3,4->5->6,return 1->2->3->4->5->6.
Given 1->3->5,2->4->4,return 1->2->3->4->5->6.
思路：
（1）题意为将两个有序链表合成一个有序链表。
（2）首先，分别对链表头结点判空，如果都为空，返回null；若L1为空，L2不为空，返回L1；如果L1为空，L2不为空，返回L2。
（2）其次，设置节点p为结果链表头结点，设置标志节点q指向结果链表尾部节点。
（3）再次，循环对待合并链表中的节点遍历，如果节点L1和L2都不为空，则比较其节点值，如果L1<L2，（第一次需要初始化p和q的值，p=L1，
q=p），将标志节点指向节点L1，标志节点后移，L1指向其后续节点，L1>=L2情况类似，直到循环结束。
（4）最后，需要判断未进行比较的节点，将这些节点追加为q的后续节点，返回p即为结果。
（5）其比较过程简单如下所示：
例如： L1: 1->3->5->13 L2: 2->4->14->17
（A）L1=1，L2=2，L1<L2，初始p=L1=1，q=p=1，L1=L1.next=3;
（B）L1=3，L2=2，L1>L2，此时，q.next=L2=2，q=q.next=2，L2=L2.next=4；
（C）L1=3，L2=4，L1<L2，此时，q.next=L1=3，q=q.next=3，L1=L1.next=5；
（D）L1=5，L2=4，L1>L2，此时，q.next=L2=4，q=q.next=4，L2=L2.next=14；
（E）L1=5，L2=14，L1<L2，此时，q.next=L1=5，q=q.next=5，L1=L1.next=13；
（F）L1=13，L2=14，L1<L2，此时，q.next=L1=13，q=q.next=13，L1=L1.next=null；
（G）由于L1为空，此时需将L2中后续节点追加到q后面即可。
算法代码实现如下所示：
public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
if (L1 == null && L2 == null return null;
if (L1 == null && L2 != null) return L2;
if (L1 != null && L2 == null) return L1;
ListNode p = null;
ListNode q = p;
while (L1 != null && L2 != null) {
if (L1.val < L2.val) {
if (p == null) {
p = L1;
q = p;
L1 = L1.next;
continue;
}
q.next = L1;
q = q.next;
L1 = L1.next;
} else {
if (p == null) {
p = L2;
q = p;
L2 = L2.next;
continue;
}
q.next = L2;
q = q.next;
L2 = L2.next;
}
}
while (L1 != null) {
q.next = L1;
q = q.next;
L1 = L1.next;
}
while (L2 != null) {
q.next = L2;
q = q.next;
L2 = L2.next;
}
return p;
}