# Definition for singly-linked list.
from abc import abstractproperty
from typing import List, Optional


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


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        if not l1 or not l2:
            return l1 or l2

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        res = ListNode()
        resNode = res

        while l1 and l2 is not None:

            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next

            resNode = resNode.next

        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2

        return res.next

5f7a6c6e421678a23980a6948b149ec8865691c4
<mask token>


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]
        ) ->Optional[ListNode]:
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[
        ListNode]) ->Optional[ListNode]:
        res = ListNode()
        resNode = res
        while l1 and l2 is not None:
            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next
            resNode = resNode.next
        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2
        return res.next

<mask token>


class ListNode:
    <mask token>


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]
        ) ->Optional[ListNode]:
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[
        ListNode]) ->Optional[ListNode]:
        res = ListNode()
        resNode = res
        while l1 and l2 is not None:
            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next
            resNode = resNode.next
        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2
        return res.next

<mask token>


class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]
        ) ->Optional[ListNode]:
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[
        ListNode]) ->Optional[ListNode]:
        res = ListNode()
        resNode = res
        while l1 and l2 is not None:
            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next
            resNode = resNode.next
        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2
        return res.next

from abc import abstractproperty
from typing import List, Optional


class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]
        ) ->Optional[ListNode]:
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[
        ListNode]) ->Optional[ListNode]:
        res = ListNode()
        resNode = res
        while l1 and l2 is not None:
            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next
            resNode = resNode.next
        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2
        return res.next

# Definition for singly-linked list.
from abc import abstractproperty
from typing import List, Optional


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


class Solution:

    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        if not l1 or not l2:
            return l1 or l2

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeTwoListsIteration(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        res = ListNode()
        resNode = res

        while l1 and l2 is not None:

            if l1.val <= l2.val:
                resNode.next = l1
                l1 = l1.next
            else:
                resNode.next = l2
                l2 = l2.next

            resNode = resNode.next

        if l1 is not None:
            resNode.next = l1
        if l2 is not None:
            resNode.next = l2

        return res.next
