#Reversing and Merging Linked Lists
# Time Complexity: O(n) — each node is processed once
# Space Complexity: O(1) — in-place, no extra memory
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 reverse(head):
    previous = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous

L = LinkedList()
L.append(5)
L.append(8)
L.append(7)
L.append(6)
print("Original List:")
L.display()
L.head = reverse(L.head)
print("Reversed List:")
L.display()