class Node:

	# Function to initialise the node object
	def __init__(self, data):
		self.data = data # Assign data
		self.next = None # Initialize next as null

# Linked List class contains a Node object
class LinkedList:

  # Function to initialize head
  def __init__(self):
    self.head = None

  # -----------------------------------------------#

  # Function to insert a new node at the beginning
  def push(self, new_data):
    new_node = Node(new_data) # 1 & 2: Allocate the Node & Put in the data
    new_node.next = self.head # 3. Make next of new Node as head
    self.head = new_node  		# 4. Move the head to point to new Node 

  # -----------------------------------------------#

  # Appends a new node at the end
  def append(self, new_data): 
    new_node = Node(new_data) 		# 1. Create a new node , 2. Put in the data , 3. Set next as None
    if self.head is None: 		    # 4. If the Linked List is empty, then make the new node as head
          self.head = new_node
          return

    last = self.head              # 5. Else traverse till the last node
    while (last.next):
        last = last.next

    last.next =  new_node 		    # 6. Change the next of last node

  # -----------------------------------------------#

  # Given a reference to the head of a list and a key, 
  # delete the first occurrence of key in linked list 
  def deleteNode(self, key): 
      
      temp = self.head       # Store head node 
      if (temp is not None):       # If head node itself holds the key to be deleted 
          if (temp.data == key): 
              self.head = temp.next
              temp = None
              return
 
      while(temp is not None):    # Search for the key to be deleted, keep track of the previous node as we need to change 'prev.next'
          if temp.data == key: 
              break
          prev = temp 
          temp = temp.next

      if(temp == None):       # if key was not present in linked list 
          return

      prev.next = temp.next      # Unlink the node from linked list 
      temp = None
  
  # -----------------------------------------------#

  def deleteNodePos(self, position):
 
      if self.head == None:      # If linked list is empty
          return

      temp = self.head      # Store head node

      if position == 0:      # If head needs to be removed
          self.head = temp.next
          temp = None
          return

      for i in range(position -1 ):      # Find previous node of the node to be deleted
          temp = temp.next
          if temp is None:
              break

      if temp is None:      # If position is more than number of nodes
          return
      if temp.next is None:
          return

      next = temp.next.next      # Node temp.next is the node to be deleted store pointer to the next of node to be deleted
      temp.next = None      # Unlink the node from linked list
      temp.next = next

  # -----------------------------------------------#

  # Printing the linked list
  def printList(self):
    print("Linked list is : ", end=' ')
    temp = self.head
    while (temp):
      if temp.next!=None:
        print (temp.data, end=' -> ')
      else:
        print (temp.data)
      temp = temp.next
      
  def findMid(self):
    if not (self.head):
      print("Linked list is empty")
    else:
      slow = self.head
      fast = self.head
      while(fast and fast.next):
        slow = slow.next
        fast = fast.next
        if fast:
          fast = fast.next
      print(slow.data)
      
  def findLength(self):
    curr = self.head
    length = 0
    while curr:
      length += 1
      curr = curr.next
    print("Length of linked list is: ",length)
    
  def findLengthRecur(self, node):
    if node is None:
      return 0
    return 1 + self.findLengthRecur(node.next)
      
llist = LinkedList()
 
llist.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(5)
llist.head.next = second; # Link first node with second
second.next = third; # Link second node with the third node
third.next = fourth;
fourth.next = fifth;
llist.printList()

print("Middle element of linked list is : ", end='')
llist.findMid()
llist.findLength()
print("Length of linked list (recursive-way) is: ", end='')
print(llist.findLengthRecur(llist.head))