Untitled

class LinkedList:
  def __init__(self, value):
    print("CREATING A NEW OBJECT. val: ", value)
    self.value = value
    self.next = None

def solution1(headOne, headTwo):
    first = headOne if headOne.value <= headTwo.value else headTwo
    second = headTwo if headTwo.value >= headOne.value else headOne
    current = first  
    
    while first.next and second:
      if first.next.value <= second.value:
          first = first.next
      else:
          tail = first.next                     # <---- creates a pointer, which is ok 
          first.next = LinkedList(second.value) # <---- creates a new object which is forbidden by the problem statement
          first.next.next = tail
          first = first.next
          second = second.next
    if second:
        first.next = second
    return current
        

def solution2(headOne, headTwo):
    one = headOne
    two = headTwo
    current = one  # Current _is not_ updated as I update one
    while one and two:
        if one.value <= two.value:
            one = one.next
        else:
            tail = one
            one = LinkedList(two.value)
            one.next = tail
            one = one.next
            two = two.next
    if two:
        one.next = two
    return current

def solution3(headA, headB):
  if headA is None and headB is None:
    return None
  
  if headA is None:
    return headB

  if headB is None:
    return headA
  
  if headA.value < headB.value:
    smallerNode = headA
    smallerNode.next = solution3(headA.next, headB)
  else:
    smallerNode = headB
    smallerNode.next = solution3(headA, headB.next)
  
  return smallerNode

# In case of solution1 - the answer is legit but you should see no 'CREATING A NEW OBJECT. val: X' messages.
# In case of 
print("SETUP")
a1 = LinkedList(1)
a2 = LinkedList(5)
a3 = LinkedList(7)
a4 = LinkedList(9)
a1.next = a2
a2.next = a3
a3.next = a4

b1 = LinkedList(2)
b2 = LinkedList(4)
b3 = LinkedList(4)
b4 = LinkedList(5)
b5 = LinkedList(8)
b6 = LinkedList(8)
b1.next = b2
b2.next = b3
b3.next = b4
b4.next = b5
b5.next = b6


print("\n\nWORK")
c = solution3(a1, b1)

print("\n\nRESULT")
while c: 
  print(c.value)
  c = c.next