【leetcode刷题】20T15-合并两个有序链表

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
        p = head
        head1, head2 = l1, l2

        # 比较两个链表节点的大小，插入新链表中
        while head1 and head2:
            if head1.val < head2.val:
                p.next = head1
                head1 = head1.next
            else:
                p.next = head2
                head2 = head2.next
            p = p.next

        # 可能链表并未访问结束
        while head1:
            p.next = head1
            head1 = head1.next
            p = p.next
        while head2:
            p.next = head2
            head2 = head2.next
            p = p.next
        return head.next