《劍指offer》之合并兩個排序的連結清單（python實作）

問題描述：

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

思路分析：

不斷對兩個連結清單目前頭指針所指向的元素值進行比較，
小的接入合并連結清單尾部，頭指針後移一位，該元素的next域改為空，直到有一個連結清單周遊完，
再将有剩餘的連結清單合并到連結清單尾部即可完成。
           

python語言代碼實作如下：

# -*- 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
        p = s = ListNode(0)
        while pHead1 != None and pHead2 != None:
            if pHead1.val <= pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        if pHead1:
            p.next = pHead1
        elif pHead2:
            p.next = pHead2
        return s.next