合并有序链表

递归版本：

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # 递归结束条件就是有一个到头了，返回不是None的那个就好了
        if not pHead1 or not pHead2: return pHead1 if pHead1 else pHead2
        # 让phead1指向小的，有必要的话交换
        if pHead1.val > pHead2.val: pHead1,pHead2 = pHead2,pHead1
        # 递归步骤
        pHead1.next = self.Merge(pHead1.next,pHead2)
        return pHead1

非递归版本：

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        p = ListNode(-1)
        ans = p
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next

        p.next = pHead1 if pHead1 else pHead2
        return ans.next