面试题25：合并两个排序的链表

题目描述：

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

解题思路：递归调用

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        l1 = pHead1
        l2 = pHead2
        if l1 == None and l2 == None:
            return None
        if l1==None and l2!=None:
            return l2
        if l1!=None and l2==None:
            return l1
        if l1!=None and l2!=None:
            if l1.val>=l2.val:
                head = l2
                head.next = self.Merge(l1,l2.next)
            else: 
                head = l1
                head.next = self.Merge(l1.next,l2)
            return head