题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路
首先是基本思路，对于两个链表，每次取较小的一个，同时把指针后移。当出现一个链表为空的时候，可以直接返回另外一个链表。 在初始情况时要考虑两个链表分别为空的情况。具体的实现可以用递归的方法实现。
代码
def Merge(self, pHead1, pHead2):
if pHead1 is None:
return pHead2
elif pHead2 is None:
return pHead1
mergeNode = ListNode(None)
if pHead1.val < pHead2.val:
mergeNode = pHead1
mergeNode.next = self.Merge(pHead1.next,pHead2)
else:
mergeNode = pHead2
mergeNode.next = self.Merge(pHead1,pHead2.next)
return mergeNode
