from utils.listNode import ListNode

class Solution:
    def merge(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        
        node1, node2 = l1, l2
        head = None
        curr = None

        while node1 and node2:
            min_value = min(node1.value, node2.value)

            if min_value == node1.value:
                node1 = node1.next
            else:
                node2 = node2.next
            
            if not head:
                head = ListNode(min_value)
                curr = head
            else:
                curr.next = ListNode(min_value)
                curr = curr.next
        
        if node1:
            curr.next = node1
        elif node2:
            curr.next = node2
        
        return head

# time: O(m + n)
# space: O(1)
class Solution2:
    def merge(self, l1, l2):
        prev = dummy = ListNode(None)

        while l1 and l2:
            if l1.value < l2.value:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            
            prev = prev.next
        
        prev.next = l1 or l2

        return dummy.next

one = ListNode(1)
two = ListNode(2)
four = ListNode(4)

one.next = two
two.next = four

one_ = ListNode(1)
three_ = ListNode(3)
four_ = ListNode(4)

one_.next = three_
three_.next = four_

print(one)
print(one_)

solution = Solution2()
print(solution.merge(one, one_))