#Reversing and Merging Linked Lists
#Time Complexity: Merge two lists O(m + n)
#Space Complexity: O(1) extra (besides output list nodes)
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class LinkedList:
  def __init__(self, head=None):
    self.head = head

  def append(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
     else:
      current = self.head
      while current.next is not None:
        current = current.next
      current.next = new_node

  def display(self):
    current = self.head
    while current is not None:
      print(current.data, end=" -> ")
      current = current.next
    print("None")

  def merge_sorted_lists(L1, L2):
    p1 = L1.head
    p2 = L2.head
    merged = LinkedList()
    tail = None
    while p1 is not None and p2 is not None:
      if p1.data < p2.data:
        new_node = Node(p1.data)
        p1 = p1.next
      else:
        new_node = Node(p2.data)
        p2 = p2.next
      if merged.head is None:
        merged.head = new_node
        tail = new_node
      else:
        tail.next = new_node
        tail = new_node

    # Add remaining nodes
    while p1 is not None:
      tail.next = Node(p1.data)
      tail = tail.next
      p1 = p1.next
    while p2 is not None:
      tail.next = Node(p2.data)
      tail = tail.next
      p2 = p2.next
    return merged

L1 = LinkedList()
L1.append(1)
L1.append(5)
L1.append(7)
L2 = LinkedList()
L2.append(2)
L2.append(3)
L2.append(6)
print("List 1:")
L1.display()
print("List 2:")
L2.display()
L3 = merge_sorted_lists(L1, L2)
print("Merged List:")
L3.display()