面试17：合并两个有序链表

【题目描述】
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
【思路】
遍历链表1和链表2，比较大小，当前谁小则加其加入结果res链表中。
【代码】

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        res=ListNode(0)
        head = res#记录头节点位置
        while pHead1!=None and pHead2!=None:
            #case1:pHead1的值大于pHead2
            if pHead1.val > pHead2.val:
                res.next = pHead2
                pHead2=pHead2.next
                res = res.next
            #case2：pHead1的值小于或等于huopHead2
            else:
                res.next = pHead1
                pHead1 = pHead1.next
                res = res.next
        if pHead1==None:
            res.next = pHead2
        if pHead2==None:
            res.next = pHead1
        return head.next