class LinkedList(object):
	def __init__(self):
		self.head = None
	def add_node(self,data,next=None):
		if self.head is None:
			print("ya")
			self.head = node(data,None)
			return
		current = self.head
		prev = None
		while current:
			prev = current
			current = current.next
		prev.next = node(data,next)
		current = prev.next
		current.next = None
	def reverse_list(self):
		current = self.head
		prev = None
		while current.next:
			temp = current
			current = current.next
			temp.next = prev
			prev = temp
			print("This is current and prev",current.data,prev.data)
		current.next = prev
		self.head = current
	def recurse_list(self):
		current = self.head
		prev = None
		self.recurse_list_Util(current,prev)				

	def search_node(self,data):
		i=0
		current = self.head
		while current:
			if current.data is data:
				return i
			current = current.next
			i+=1
		print("No such node")
						
	def recurse_list_Util(self,current,prev):
		if current.next is None:
			self.head = current
			current.next = prev
			return
		temp = current.next
		current.next = prev
		prev = current
		self.recurse_list_Util(temp,prev)

	def reverse_knodes(self,k):
		head = self.head
		current = self.head
		prev = None
		temp = None
		i=0
		#print k
		while current and (i<k):
			temp = current.next
			current.next = prev
			prev = current
			current = temp
			i=i+1
			#print i
		self.head = prev	
		if temp:
			head.next = self.reverse_knodes_Util(temp,k)
		return prev		
	def reverse_knodes_Util(self,head,k):
		current = head
		prev = None
		temp = None
		i=0
		while current and (i<k):
			temp = current.next
			current.next = prev
			prev = current
			current = temp
			i = i+1
		if temp:
			head.next = self.reverse_knodes_Util(temp,k)
		return prev			
	def display(self):
		if self.head is None:
			print("No node")
			return
		current = self.head
		while current:
			print(current.data)
			current = current.next			
class node(object):
	def __init__(self,data,next):
		self.data = data
		self.next = next

l = LinkedList()
l.add_node(1)
l.add_node(2)
l.add_node(3)
l.add_node(4)
l.add_node(5)
l.add_node(6)
l.add_node(7)
l.add_node(8)
l.add_node(9)
l.display()
l.reverse_list()
print("after reverse_list")
l.display()
l.recurse_list()
print("after recurse_list")
l.display()
print("after reverse_knodes")
l.reverse_knodes(3)
l.display()
pos = l.search_node(2)
print(pos)