难度：简单

知识点：链表

地址：https://leetcode-cn.com/problems/merge-two-sorted-lists

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

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

思路

• 因为两个链表都是升序的，所以我们可以同时遍历两个链表，并一一对比，将较小的值依次添加到新链表中
• 最后将没有遍历完的链表直接添加到新链表后面即可

from utils import ListNode
from utils import array2listnode
from utils import listnode2array

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        l3 = ListNode(0)
        l4 = l3
        while l1 and l2:
            val1 = l1.val
            val2 = l2.val
            if val1 <= val2:
                l4.next = ListNode(val1)
                l1 = l1.next
            elif val1 > val2:
                l4.next = ListNode(val2)
                l2 = l2.next
            l4 = l4.next
        
        if l1:
            l4.next = l1
        if l2:
            l4.next = l2
        return l3.next
                
        
    
s = Solution()
l1 = array2listnode([1, 2, 4])
l2 = array2listnode([1, 3, 4])
assert listnode2array(s.mergeTwoLists(l1, l2)) == [1, 1, 2, 3, 4, 4]