合并两个排序链表

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