LintCode 165 题
将两个排序链表合并为一个新的排序链表
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null
使用 python 语言实现：
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
def merge_two_lists(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1
head = None
current = None
while l1 is not None and l2 is not None:
if l1.val < l2.val:
if head is None:
head = current = l1
else:
current.next = l1
current = l1
l1 = l1.next
else:
if head is None:
head = current = l2
else:
current.next = l2
current = l2
l2 = l2.next
if l1 is None:
current.next = l2
else:
current.next = l1
return head
"""
递归
@param: l1: ListNode l1 is the head of the linked list
@param: l2: ListNode l2 is the head of the linked list
@return: ListNode head of linked list
"""
def merge_two_lists_recursive(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val < l2.val:
head = l1
head.next = self.merge_two_lists_recursive(l1.next, l2)
else:
head = l2
head.next = self.merge_two_lists_recursive(l1, l2.next)
return head
# 测试代码1，建立链表：1->3->8->11->15->None
l1_0 = ListNode(1)
l1_1 = ListNode(3)
l1_2 = ListNode(8)
l1_3 = ListNode(11)
l1_4 = ListNode(15)
l1_0.next = l1_1
l1_1.next = l1_2
l1_2.next = l1_3
l1_3.next = l1_4
# 建立链表：2->None
l2_0 = ListNode(2)
s1 = Solution().merge_two_lists(l1_0, l2_0)
while s1:
print s1.val
s1 = s1.next
# 测试代码2，建立链表：1->3->8->11->15->None
l1_0 = ListNode(1)
l1_1 = ListNode(3)
l1_2 = ListNode(8)
l1_3 = ListNode(11)
l1_4 = ListNode(15)
l1_0.next = l1_1
l1_1.next = l1_2
l1_2.next = l1_3
l1_3.next = l1_4
# 建立链表：2->None
l2_0 = ListNode(2)
s2 = Solution().merge_two_lists_recursive(l1_0, l2_0)
while s2:
print s2.val
s2 = s2.next
