劍指offer刷題（十五）合并兩個排序的連結清單

合并兩個排序的連結清單（python）

題目

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

思路

由于兩個連結清單都是遞增的，是以每次共同比較兩個連結清單中最小的值，把比較小的值插入到新的連結清單中，一直循環，直到某個連結清單為空，再把另外一個不為空的連結清單插入到新的連結清單中。

代碼

class Solution:
    # 傳回合并後清單
    def Merge(self, pHead1, pHead2):
        # write code here
        #初始化一個節點值為0的空節點
        pHead = ListNode(0)
        #把pHead的指向用temp儲存下來
        temp = pHead
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                pHead.next = pHead1
                pHead = pHead.next
                pHead1 = pHead1.next
            else:
                pHead.next = pHead2
                pHead = pHead.next
                pHead2 = pHead2.next
        if pHead1 == None:
            pHead.next = pHead2
        if pHead2 == None:
            pHead.next = pHead1
        return temp.next