【剑指offer】合并两个排序的链表（python）

题目描述：

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

解析：
本题要求对两个单调递增的链表进行合并，且合并后的链表需满足单调不减的规则：
1、首先需要判断输入的两个链表中是否存在空链表，若其中一个链表为空，则返回另一个链表：

if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1

2、创建头结点，使它的值等于两个链表的头结点中较小的值，并创建头结点的copy，以便最终的返回：

if pHead1.val > pHead2.val:
            temp.val = pHead2.val
        temp_copy = temp

3、使用while循环遍历第一个链表，并创建临时节点v，使它的值等于第一个链表当前节点的值，然后使用while循环在第二个链表中进行遍历，若存在节点值小于临时节点v的，直接将该节点作为合并链表的下一节点：

while pHead1.next:
            pHead1 = pHead1.next
            v = pHead1.val
            while pHead2 and pHead2.val < v:
                temp_copy.next = ListNode(pHead2.val)
                temp_copy = temp_copy.next
                pHead2 = pHead2.next
            temp_copy.next = ListNode(v)
            temp_copy = temp_copy.next

4、继续使用while循环遍历第二个链表，将上一次while循环中未添加的节点直接添加到当前合并链表之后：

while pHead2:
            temp_copy.next = ListNode(pHead2.val)
            temp_copy = temp_copy.next
            pHead2 = pHead2.next

完整代码：

# -*- 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
        if not pHead2:
            return pHead1
        temp = ListNode(pHead1.val)
        if pHead1.val > pHead2.val:
            temp.val = pHead2.val
        temp_copy = temp
        while pHead1.next:
            pHead1 = pHead1.next
            v = pHead1.val
            while pHead2 and pHead2.val < v:
                temp_copy.next = ListNode(pHead2.val)
                temp_copy = temp_copy.next
                pHead2 = pHead2.next
            temp_copy.next = ListNode(v)
            temp_copy = temp_copy.next
        while pHead2:
            temp_copy.next = ListNode(pHead2.val)
            temp_copy = temp_copy.next
            pHead2 = pHead2.next
        return temp