311 合并有序链表2 #

1. 构造链表
2. 合并有序链表的实现

构造链表 #

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

合并有序链表的实现 #

采用递归方式合并链表，合并后递归输出结果

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

def mergeTwoLists(l1, l2):
    if l1 is None:
        return l2
    elif l2 is None:
        return l1
    elif l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

def printListNode(L):
    if(L is not None):
        print(L.val)
        printListNode(L.next)
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

printListNode( mergeTwoLists(l1,l2)  )

小结 #

习题 #

1. 思考递归中是如何保证返回的是合并链表的头结点的
2. 尝试使用迭代方式完成合并