什么是合并两个有序链表
假设有两条链表，这两条链表分别都是升序排列的，如下图所示：
现在要求将二者合并成一条链表，并且该链表也是升序排列的，合并后的链表如下图所示：
思路
如果对归并排序有所了解，那么这个问题就很简单。在归并排序的递归过程中，我们的算法是将原始数组a切割成两段：a1和a2，对a1和a2分别排序后，再将二者归并成一个有序的数组。这里的思路是一样的，只不过将数组变成了链表。
大体的思路是：
- 确定合并后的新链表的头节点
head - 使用一个指针
l3，初始化为head，用这个指针来组织新链表的各个节点 - 使用两个指针
l1和l2，分别初始化为两条原始链表的头节点，用来遍历这两条链表。 - 当
l1的值小于等于l2的值时，那么令l3->next=l1，否则令l3->next=l2 - 一般情况下，有一个链表会提前遍历结束，例如链表1首先遍历结束，也就是
l1=Null时，那么由于另一条链表本身就是有序的，此时直接令l3->next=l2，就可以完成合并操作了。
哨兵方法简化代码
如果直接按上述思路编码，那么确定新链表的头节点head需要编写额外的代码。但仔细想想，确定新链表head的过程无非是比较l1 head和l2 head的值，将其中较小值的那个节点作为新链表的head，这个操作和后续遍历两条链表的比较操作的逻辑是一致的。为了避免这种冗余代码（以及处理各种边界问题），可以考虑一种哨兵方法。也就是，虚拟一个节点prehead，认为它的下一个节点就是新链表的头节点head，并让l3=prehead，从这个虚拟节点开始组织新的链表，这样就无需对确定头节点的操作做特殊处理了。在最后整理好新的链表时，我们直接返回prehead->next，得到的自然就是l3的头节点了。
代码实现
下面给出Python代码的一个实现：
class Solution:
def mergeTwoLists(self, l1, l2):
# 新建一个虚拟节点作为哨兵节点
# 作为目标链表l3头节点的前面一个节点
prehead = ListNode(-1)
# 利用prev节点来组织新的链表
prev = prehead
# 循环截至条件是l1和l2其中任意一个链表已经遍历完
while l1 and l2:
# 比较l1和l2指向的节点的值
# 将值比较小的那个加入到新链表中
# 然后将该链表过渡到下一个节点
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# 将还没有遍历完的那个链表直接添加到新链表的末尾
prev.next = l1 if l1 is not None else l2
# 返回的是哨兵节点的下一个节点，也就是新链表的头节点
return prehead.next
