#!/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
近期评论