题解 | 合并两个排序的链表---leetcode23

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def Merge1(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        newHead=ListNode(0)
        cur=newHead
        cur1=pHead1
        cur2=pHead2
        if not cur1:
            return pHead2
        if not cur2:
            return pHead1

        while cur1 and cur2:
            if cur1.val<=cur2.val:
                cur.next=cur1
                cur1=cur1.next 
                #if cur1:
                    #print("cur1",cur.val,cur1.val)
            
            else:
                cur.next=cur2
               
                cur2=cur2.next
                #if cur2:
                    #print("cur2",cur2.val)
            cur=cur.next
        if not cur2:
                cur.next=cur1
        else :
                cur.next=cur2
        #print(newHead.next.val)
        return newHead.next

    """
    递归写法

    1.如果一个链表为空返回另外一个链表
    2. 如果pHead1 节点比pHead2 ，下一个节点应该是pHead1 ，应该return pHead1 
     在ruturn 之前递归 pHead1.next 和pHead2 合并的头结点
     如果 pHead1 节点比pHead2 大， 下一个节点应该是pHead2, 应该return pHead2 ，在return 之前，指定
     pHead2 的下一个节点应该是pHead1和pHead2.next 合并的头结点
    """
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # 1. 其中一个为空返回另外一个
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        # 两个链表都不为空
        if pHead1.val<=pHead2.val:
            pHead1.next=self.Merge(pHead1.next,pHead2)
            return pHead1 

        else :
            pHead2.next =self.Merge(pHead1,pHead2.next )
            return pHead2