合并两个排好序的链表

#!/usr/bin/env python
# -*- coding_utf-8 -*-

from get_linked_list import Get_linked_list

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

def Merge1(phead1, phead2):
    """ 递归版本 """
    if (phead1 == None):
        return phead2
    if (phead2 == None):
        return phead1

    if phead1.val > phead2.val:
        merged_head = phead2
        merged_head.next = Merge1(phead2.next, phead1)
    else:
        merged_head = phead1
        merged_head.next = Merge1(phead1.next, phead2)

    return merged_head

def Merge2(phead1, phead2):
    """非递归版本"""

    if (phead1 == None):
        return phead2
    if (phead2 == None):
        return phead1
    merged_head = ListNode(None)
    new_head = merged_head
    while (phead1 != None ) and (phead2 != None):
        if (phead1.val > phead2.val):
            cur = phead2
            phead2 = phead2.next
        else:
            cur = phead1
            phead1 = phead1.next

        merged_head.next = cur
        merged_head = merged_head.next

    if phead1 == None:
        merged_head.next = phead2
    elif phead2 == None:
        merged_head.next = phead1

    return new_head.next

if __name__ == '__main__':

    # 正常情况
    ll1 = Get_linked_list([1,2,3,5,7]).get_data()
    ll2 = Get_linked_list([2,4,6,8]).get_data()

    res = Merge2(ll1, ll2)
    while res != None:
        print(res.val)
        res = res.next
    print('-' * 10)

    # 一个为空指针

    ll1 = Get_linked_list([1, 2, 3, 5, 7]).get_data()
    ll2 = Get_linked_list([]).get_data()

    res = Merge2(ll1, ll2)
    while res != None:
        print(res.val)
        res = res.next

    print('-' * 10)

    # 两个为空指针

    ll1 = Get_linked_list([]).get_data()
    ll2 = Get_linked_list([]).get_data()

    res = Merge2(ll1, ll2)
    while res != None:
        print(res.val)
        res = res.next