連結清單-（合并兩個有序連結清單）算法

# -*- coding:utf-8 -*-

""" 
Author: leadingme
Mail:[email protected]
MyWebsite:leadingme.top
"""

# 合并兩個有序連結清單
"""
    算法要求:
        将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單所有節點組成的。
    示例:
        輸入: 1->2->4, 1->3->4
        輸出: 1->1->2->3->4->4
"""

def mergeTwoLists(l1, l2):
    """

    :type l1: LinkNode
    :param l2: LinkNode
    :return:
    """
    if l1 is None and l2 is None: # 兩條連結清單為空連結清單
        return None
    fakeNode = LinkNode(0) # 建立一個val為0的新節點，用來作為新連結清單的頭節點
    pointer = fakeNode
    while l1 is not None or l2 is not None:
        if l1 is None: # l1連結清單為空, l2連結清單為非空, 周遊完整個l2
            pointer.next = l2
            l2 = l2.next
            pointer = pointer.next
        elif l2 is None:
            pointer.next = l1
            l1 = l1.next
            pointer = pointer.next
        else:
            if l1.val <= l2.val:  # 如果兩個連結清單都不為空，則比較l1.val和l2.val,較小的放前面
                pointer.next = l1
                l1 = l1.next
                pointer = pointer.next
            else:
                pointer.next = l2
                l2 = l2.next
                pointer = pointer.next
        return fakeNode.next