剑指offer 面试25题

面试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

        if not pHead1:

            return pHead2

        elif not pHead2:

            return pHead1

        pMergedHead=None

        if (pHead1.val<pHead2.val):

            pMergedHead=pHead1

            pMergedHead.next=self.Merge(pHead1.next,pHead2)

        else:

            pMergedHead=pHead2

            pMergedHead.next=self.Merge(pHead1,pHead2.next)

        return pMergedHead