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

一、python链表结构

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

二、输入、输出

输入：两个有序链表的头结点

输出：新链表的头结点

@param pHead1 ListNode类 
@param pHead2 ListNode类 
@return ListNode类

三、解题思路

1. 另需4个指针：

①newHead，用于最后返回新链表的头结点，始终指向新链表第一个元素不动。

②pTmp1,pTmp2分别指向两个有序链表的 第一个待处理结点

③previous，指向已经完成排序的新链表的最后一个结点，用previous.next连接下一个加入的有序结点。

2. 初始状态，中间状态，图示：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        newHead=pHead1 if pHead1.val<pHead2.val else pHead2
        
        if newHead==pHead1:
            pTmp1=pHead1.next
            pTmp2=pHead2
        else:
            pTmp2=pHead2.next
            pTmp1=pHead1
            
        previous=newHead
        
        while pTmp1 and pTmp2:
            if pTmp1.val<=pTmp2.val:
                previous.next=pTmp1
                pTmp1=pTmp1.next
            else:
                previous.next=pTmp2
                pTmp2=pTmp2.next
            previous=previous.next   
            
        if pTmp1==None:
            previous.next=pTmp2
        else:
            previous.next=pTmp1
        
        return newHead