Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed (See Example 2 for clarification).
Example 1:
Input:
LinkedList: 1->2->2->4->5->6->7->8
K = 4
Output: 4 2 2 1 8 7 6 5 
Explanation: 
The first 4 elements 1,2,2,4 are reversed first 
and then the next 4 elements 5,6,7,8. Hence, the 
resultant linked list is 4->2->2->1->8->7->6->5.
Example 2:
Input:
LinkedList: 1->2->3->4->5
K = 3
Output: 3 2 1 5 4 
Explanation: 
The first 3 elements are 1,2,3 are reversed 
first and then elements 4,5 are reversed.Hence, 
the resultant linked list is 3->2->1->5->4.
Your Task:
You don't need to read input or print anything. Your task is to complete the function reverse() which should reverse the linked list in group of size k and return the head of the modified linked list.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 10^{4}
1 <= k <= N

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
"""Return reference of new head of the reverse linked list

  The input list will have at least one element

  Node is defined as



class Node:

    def __init__(self, data):

		self.data = data

		self.next = None

  This is method only submission.

  You only need to complete the method.

"""

class Solution:

    def reverse(self,head, k):

        # Code here

Solutions:
class Solution:

	def reverse(self, head, k):
		curr = head
		prev = None
		if k <= 1 or curr is None:
			return head
		cnt = k
		while curr and cnt > 0:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
			cnt -= 1
		head.next = self.reverse(curr, k)
		return prev


class Solution:

	def reverse(self, head, k):
		if head == None or head.next == None:
			return head
		prev = None
		curr = head
		next = None
		count = 0
		while curr != None and count < k:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
			count += 1
		if next != None:
			head.next = self.reverse(next, k)
		return prev


class Solution:

	def reverse(self, head, k):
		if head is None:
			return None
		if k == 1:
			return head
		A = None
		B = head
		C = None
		z = k
		while B and z:
			C = B.next
			B.next = A
			A = B
			B = C
			z = z - 1
		head.next = self.reverse(B, k)
		return A


class Solution:

	def reverse(self, head, k):
		prev = None
		cur = head
		next = None
		count = 0
		while cur is not None and count < k:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
			count += 1
		if next is not None:
			head.next = self.reverse(next, k)
		return prev


class Solution:

	def fun(self, head, k):
		if head is None:
			return None
		prev = None
		curr = head
		c = 0
		while curr is not None and c < k:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
			c += 1
		head.next = self.fun(curr, k)
		return prev

	def reverse(self, head, k):
		return self.fun(head, k)


class Solution:

	def reverse(self, head, k):
		if not head:
			return None
		current = head
		start = head
		prev = None
		iterarion = 0
		current_next = None
		while current and iterarion < k:
			current_next = current.next
			current.next = prev
			prev = current
			current = current_next
			iterarion += 1
		if current:
			start.next = self.reverse(current, k)
		return prev


class Solution:

	def reverse(self, head, k):
		if head == None:
			return
		prev = None
		itr = head
		cnt = 0
		while itr and cnt < k:
			nxt = itr.next
			itr.next = prev
			prev = itr
			itr = nxt
			cnt += 1
		if nxt != None:
			head.next = self.reverse(nxt, k)
		return prev


class Solution:

	def reverse(self, head, k):
		i = 1
		imp = head
		temp = head
		prev = head
		cur = head.next
		if head != None and head.next != None:
			first = head.next.next
		prev.next = None
		while cur != None and i < k:
			cur.next = prev
			prev = cur
			cur = first
			if first != None:
				first = first.next
			i += 1
		temp = prev
		i = 1
		head = cur
		prev = head
		if head != None:
			cur = head.next
		if head != None and head.next != None:
			first = head.next.next
		while cur != None:
			if i == k:
				i = 1
				imp.next = prev
				imp = head
				imp.next = None
				prev = cur
				head = prev
				cur = first
				if first != None:
					first = first.next
			else:
				cur.next = prev
				prev = cur
				cur = first
				if first != None:
					first = first.next
				i += 1
		imp.next = prev
		if head != None:
			head.next = None
		return temp


class Solution:

	def reverse(self, head, k):
		if head is None:
			return
		prev = None
		ptr = head
		c = 0
		while ptr and c < k:
			nptr = ptr.next
			ptr.next = prev
			prev = ptr
			ptr = nptr
			c += 1
		if nptr:
			head.next = self.reverse(nptr, k)
		return prev


class Solution:

	def reverse(self, start, k):
		if start.next is None:
			return start
		curr = start
		prev = None
		count = 0
		while curr and count < k:
			forw = curr.next
			curr.next = prev
			prev = curr
			curr = forw
			count += 1
		if curr:
			start.next = self.reverse(curr, k)
		return prev


class Solution:

	def reverse(self, head, k):
		dummy = Node(-1)
		dummy.next = head
		groupPrev = dummy
		while True:
			kth = self.getKthFromNode(groupPrev, k)
			if not kth:
				break
			groupNext = kth.next
			(prev, curr) = (groupNext, groupPrev.next)
			while curr != groupNext:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			temp = groupPrev.next
			groupPrev.next = kth
			groupPrev = temp
		return dummy.next

	def getKthFromNode(self, node, k):
		if not node.next:
			return None
		while node and k > 0:
			node = node.next
			k -= 1
			if node.next == None and k > 0:
				return node
		return node


class Solution:

	def reverse(self, head, k):
		if head is None:
			return head
		(p, c, n) = (None, head, None)
		res = 0
		while c is not None and res < k:
			n = c.next
			c.next = p
			p = c
			c = n
			res += 1
		if c is not None:
			head.next = self.reverse(c, k)
		return p


class Solution:

	def reverse(self, head, k):
		if head is None or k == 1:
			return head

		def reverse_list(node, k):
			prev = None
			curr = node
			count = 0
			while curr and count < k:
				next_node = curr.next
				curr.next = prev
				prev = curr
				curr = next_node
				count += 1
			if next_node:
				node.next = reverse_list(next_node, k)
			return prev
		return reverse_list(head, k)


class Solution:

	def reverse(self, head, k):
		if not head:
			return head
		nextone = None
		prev = None
		curr = head
		ct = 1
		while curr != None and ct <= k:
			nextone = curr.next
			curr.next = prev
			prev = curr
			curr = nextone
			ct += 1
		if nextone != None:
			head.next = Solution.reverse(self, nextone, k)
		return prev


class Solution:

	def reverse(self, head, k):
		nonCurr = head
		first = True
		while nonCurr != None:
			curr = head
			prev = None
			count = 0
			while curr != None and count < k:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
				count += 1
			if first:
				firstprev = prev
				first = False
			else:
				olderhead.next = prev
			olderhead = head
			head = curr
			nonCurr = curr
		return firstprev


class Solution:

	def reverse(self, head, k):
		noneCurr = head
		first = True
		while noneCurr != None:
			prev = None
			curr = head
			count = 0
			while curr != None and count < k:
				temp = curr.next
				curr.next = prev
				prev = curr
				count += 1
				curr = temp
			if first:
				finalreturn = prev
				first = False
			else:
				oldhead.next = prev
			oldhead = head
			head = curr
			noneCurr = curr
		return finalreturn


class Solution:

	def reverse(self, head, k):
		c = 0
		prev = None
		cur = head
		while cur and c < k:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
			c += 1
		if next:
			head.next = self.reverse(next, k)
		return prev


class Solution:

	def reverse(self, head, k):
		if not head:
			return None
		forw = prev = None
		count = 0
		curr = head
		while curr and count < k:
			forw = curr.next
			curr.next = prev
			prev = curr
			curr = forw
			count += 1
		if forw != None:
			head.next = self.reverse(forw, k)
		else:
			head.next = None
		return prev


class Solution:

	def reverse(self, head, k):
		if head == None or k == 1:
			return head
		prev = None
		curr = head
		end = head
		n = k
		while curr != None and n > 0:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
			n -= 1
		end.next = self.reverse(curr, k)
		return prev


class Solution:

	def reverse(self, head, k):
		curr = head
		prev = None
		start = head
		n = None
		count = k
		while curr is not None and count > 0:
			n = curr.next
			curr.next = prev
			prev = curr
			curr = n
			count -= 1
		if curr is not None:
			head.next = self.reverse(curr, k)
		return prev


class Solution:

	def reverseSubarray(self, first, last):
		prev = None
		curr = first
		mynext = first
		while curr != last:
			mynext = curr.next
			curr.next = prev
			prev = curr
			curr = mynext
		newFirst = prev
		newLast = first
		return [newFirst, newLast]

	def reverse(self, head, k):
		first = head
		prevLast = None
		while first != None:
			last = first
			for i in range(k):
				if last == None:
					break
				last = last.next
			[newFirst, newLast] = self.reverseSubarray(first, last)
			if first == head:
				head = newFirst
			if prevLast != None:
				prevLast.next = newFirst
			prevLast = newLast
			newLast.next = last
			first = last
		return head


class Solution:

	def subReverse(self, head):
		prev = None
		curr = nextt = head
		while curr != None:
			nextt = curr.next
			curr.next = prev
			prev = curr
			if prev.next == None:
				subTail = prev
			curr = nextt
		subHead = prev
		return (prev, subHead, subTail)

	def reverse(self, head, k):
		subHead = temp = head
		flag = 0
		subTail = prevSubHead = head
		count = 0
		while temp != None:
			count = count + 1
			if k == count:
				subTail = temp
				temp = temp.next
				subTail.next = None
				(revSub, subHead, subTail) = self.subReverse(subHead)
				flag += 1
				if flag == 1:
					prevSubHead = subTail
					head = revSub
				else:
					prevSubHead.next = revSub
					prevSubHead = subTail
				if temp != None:
					subTail.next = temp
					subHead = temp
				count = 0
			else:
				temp = temp.next
		if count > 0:
			subHead = subTail.next
			(revSub, subHead, subtail) = self.subReverse(subHead)
			prevSubHead.next = revSub
		return head


class Solution:

	def reverse(self, head, k):
		prev = None
		i = 0
		curr = head
		while curr != None and i < k:
			tmp = curr.next
			curr.next = prev
			prev = curr
			curr = tmp
			i += 1
		i = 0
		if tmp != None:
			head.next = self.reverse(tmp, k)
		head = prev
		return head


class Solution:

	def reverse(self, head, k):
		temp_list1 = []
		temp_list2 = []
		count = 0
		while head != None:
			count += 1
			temp_list2.append(head.data)
			head = head.next
			if count % k == 0:
				temp_list2.reverse()
				temp_list1 += temp_list2
				temp_list2 = []
		temp_list2.reverse()
		temp_list1 += temp_list2
		new_head = Node(temp_list1[0])
		temp = new_head
		for el in temp_list1[1:]:
			temp.next = Node(el)
			temp = temp.next
		return new_head


class Solution:

	def reverse(self, head, k):
		(cur, newHead, prevTail) = (head, None, None)
		while cur:
			(i, curTail, curHead) = (1, cur, None)
			while i <= k and cur:
				tmp = cur.next
				cur.next = curHead
				curHead = cur
				cur = tmp
				i += 1
			if prevTail == None:
				newHead = curHead
			elif prevTail != None:
				prevTail.next = curHead
			prevTail = curTail
		return newHead


class Solution:

	def rever(self, head, last):
		prev = None
		next = head
		temp = head
		while temp != last:
			next = temp.next
			temp.next = prev
			prev = temp
			temp = next
		return prev

	def reverse(self, head, k):
		if head == None:
			return None
		prev = None
		count = 0
		temp = head
		next = head
		while temp != None and count < k:
			next = temp.next
			temp.next = prev
			prev = temp
			temp = next
			count += 1
		head.next = self.reverse(temp, k)
		return prev


class Solution:

	def reverse(self, head, k):
		lis = []
		itr = head
		mis = []
		while itr:
			if len(lis) < k:
				lis.append(itr.data)
			else:
				mis += lis[::-1]
				lis = []
				lis.append(itr.data)
			itr = itr.next
		mis += lis[::-1]
		ans = pre = Node(-1)
		for i in mis:
			pre.next = Node(i)
			pre = pre.next
		return ans.next


class Solution:

	def reverse(self, head, k):
		a = head
		p = []
		while a is not None:
			p.append(a.data)
			a = a.next
		m = []
		for i in range(0, len(p), k):
			q = p[i:i + k]
			m += q[::-1]
		head2 = None
		b = None
		for i in m:
			s = Node(i)
			if head2 is None:
				head2 = s
				b = head2
			else:
				b.next = s
				b = b.next
		return head2


class Solution:

	def reverse(self, head, k):
		n = head
		L = []
		while n is not None:
			L.append(n.data)
			n = n.next
		L1 = []
		while True:
			if len(L) >= k:
				a = L[0:k]
				a.reverse()
				L1 = L1 + a
				L = L[k:]
			else:
				break
		if L:
			L.reverse()
			L1 = L1 + L
		n = head
		while n is not None:
			n.data = L1.pop(0)
			n = n.next
		return head


class Solution:

	def reverse(self, head, k):
		prev = None
		currnode = head
		nextnode = head
		count = 0
		while count < k and nextnode != None:
			nextnode = nextnode.next
			currnode.next = prev
			prev = currnode
			currnode = nextnode
			count += 1
		if nextnode != None:
			head.next = self.reverse(nextnode, k)
		head = prev
		return head


class Solution:

	def reverse(self, head, k):
		if head == None:
			return None
		prev = None
		curr = head
		nxt = None
		kk = k
		while curr and kk > 0:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
			kk -= 1
		if next != None:
			head.next = self.reverse(nxt, k)
		return prev


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def reverse(self, head, k):
		if head == None:
			return None
		current = head
		next = None
		prev = None
		count = 0
		while current is not None and count < k:
			next = current.next
			current.next = prev
			prev = current
			current = next
			count += 1
		if next is not None:
			head.next = self.reverse(next, k)
		return prev


class Solution:

	def reverse(self, head, k):
		start = head
		head = Node(0)
		t1 = head
		while start is not None:
			i = 1
			end = start
			while end.next is not None and i < k:
				end = end.next
				i += 1
			t2 = end.next
			end.next = None
			self.reverseList(start)
			t1.next = end
			t1 = start
			start = t2
		return head.next

	def reverseList(self, cur):
		prev = None
		while cur is not None:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt


class Solution:

	def reverse(self, head, k):
		if not head:
			return
		dummy = Node(0)
		(prev, curr) = (dummy, head)
		for i in range(k):
			dummy_next = dummy.next
			nxt = curr.next
			dummy.next = curr
			curr.next = dummy_next
			(prev, curr) = (curr, nxt)
			if not curr:
				break
		head.next = self.reverse(curr, k)
		return dummy.next


class Solution:

	def reverse(self, head, k):
		lst = []
		while head != None:
			lst.append(head.data)
			head = head.next
		lst2 = []
		for i in range(0, len(lst), k):
			b = lst[i:i + k]
			b = b[::-1]
			lst2 += b
		a = Node(0)
		temp = a
		for i in lst2:
			temp.next = Node(i)
			temp = temp.next
		return a.next


class Solution:

	def reverse(self, head, k):
		if head == None:
			return None
		current = head
		prev = None
		ref = None
		c = 0
		while current is not None and c < k:
			ref = current.next
			current.next = prev
			prev = current
			current = ref
			self.head = prev
			c += 1
		if ref is not None:
			head.next = self.reverse(ref, k)
		return prev


class Solution:

	def reverse(self, head, k):
		(prev_node, curr_node) = (None, head)
		c = 0
		while curr_node is not None and c < k:
			next_node = curr_node.next
			curr_node.next = prev_node
			prev_node = curr_node
			curr_node = next_node
			c += 1
		if next_node is not None:
			head.next = self.reverse(next_node, k)
		return prev_node


class Solution:

	def reverse(self, head, k):
		previous = None
		count = 0
		curr = head
		while curr != None and count < k:
			temp = curr.next
			curr.next = previous
			previous = curr
			curr = temp
			count = count + 1
		if temp != None:
			head.next = self.reverse(temp, k)
		head = previous
		return head


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def reverse(self, head, k):
		if head == None:
			return head
		new_head = None
		count = k
		while count != 0 and head != None:
			if count == k:
				tail = Node(head.data)
			temp = Node(head.data)
			temp.next = new_head
			new_head = temp
			head = head.next
			count -= 1
		temp = new_head
		while temp.next != None:
			temp = temp.next
		tail = temp
		tail.next = self.reverse(head, k)
		return new_head


class Solution:

	def reverse(self, head, k):
		l1 = []
		l2 = []
		temp = head
		while temp:
			l1.append(temp.data)
			temp = temp.next
		i = 0
		j = k
		while i < len(l1):
			temp = list(l1[i:k])
			for l in reversed(temp):
				l2.append(l)
			i = k
			k = k + j
		head = None
		obj = LinkedList()
		for i in reversed(l2):
			obj.push(i)
		return obj.head


class Solution:

	def reverse(self, head, k):
		tail = None
		res_h = None
		source = head
		curr = None
		count = 0
		while source:
			node = source
			source = source.next
			node.next = curr
			curr = node
			count += 1
			if count == k:
				if tail:
					tail.next = curr
				else:
					tail = curr
					res_h = tail
				while tail.next:
					tail = tail.next
				curr = None
				count = 0
		if count > 0:
			if tail:
				tail.next = curr
			else:
				tail = curr
				res_h = tail
		return res_h


class Solution:

	def length(head):
		x = head
		l = 0
		while x.next:
			x = x.next
			l += 1
		return l

	def reverse(self, head, k):
		le = Solution.length(head)
		dummyhead = Node(0)
		dummyhead.next = head
		prev = dummyhead
		curr = head
		while True:
			curr = prev.next
			if curr is None:
				break
			nex = curr.next
			for i in range(1, k):
				if nex is None:
					return dummyhead.next
				curr.next = nex.next
				nex.next = prev.next
				prev.next = nex
				nex = curr.next
			prev = curr
		return dummyhead.next


class Solution:

	def reverse(self, head, k):
		flag = False
		prev = None
		tmp = None
		while head:
			c = k
			top = head
			pre = None
			while head and c:
				nxt = head.next
				head.next = pre
				pre = head
				head = nxt
				c -= 1
			if prev:
				prev.next = pre
				prev = top
			else:
				prev = top
				tmp = pre
		return tmp


class Solution:

	def reverse(self, head, k):
		l = []
		x = []
		while head != None:
			l.append(head.data)
			head = head.next
		for i in range(0, len(l) - k + 1, k):
			y = l[i:i + k]
			x.extend(y[-1::-1])
		if len(l) % k != 0:
			y = l[len(l) - len(l) % k:]
			x.extend(y[-1::-1])
		head = Node(x[0])
		z = head
		for i in range(1, len(x)):
			y = Node(x[i])
			z.next = y
			z = y
		return head


class Solution:

	def reverse(self, head, k):
		index = 0
		prev = None
		current = head
		nextNode = head
		while current is not None and index < k:
			nextNode = current.next
			current.next = prev
			prev = current
			current = nextNode
			index += 1
		if nextNode is not None:
			head.next = self.reverse(nextNode, k)
		return prev


class Solution:

	def reverse(self, head, k):
		p = head
		curr = head
		prev = None
		l = 0
		while curr != None and l < k:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
			l += 1
		if curr:
			head.next = self.reverse(curr, k)
		return prev