合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路

首先是基本思路，对于两个链表，每次取较小的一个，同时把指针后移。当出现一个链表为空的时候，可以直接返回另外一个链表。 在初始情况时要考虑两个链表分别为空的情况。具体的实现可以用递归的方法实现。

代码

    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