Given a linked list and positions m and n. Reverse the linked list from position m to n.
Example 1:
Input :
N = 10
Linked List = 1->7->5->3->9->8->10
                      ->2->2->5->NULL
m = 1, n = 8
Output : 2 10 8 9 3 5 7 1 2 5 
Explanation :
The nodes from position 1 to 8 
are reversed, resulting in 
2 10 8 9 3 5 7 1 2 5.
Example 2:
Input:
N = 6
Linked List = 1->2->3->4->5->6->NULL
m = 2, n = 4
Output: 1 4 3 2 5 6
Explanation:
Nodes from position 2 to 4 
are reversed resulting in
1 4 3 2 5 6.
Your task :
You don't need to read input or print anything. Your task is to complete the function reverseBetween() which takes the head of the linked list and two integers m and n as input and returns the head of the new linked list after reversing the nodes from position m to n.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=10^5

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3



'''

# Node Class

class Node:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None

'''



class Solution:

    def reverseBetween(self, head, m, n):

        #code here

Solutions:
class Solution:

	def reverseBetween(self, head, m, n):
		ptr = head
		count = 1
		prev = None
		pptr = None
		h = None
		while ptr:
			if count >= m:
				h = ptr
				while count <= n:
					nptr = ptr.next
					ptr.next = prev
					prev = ptr
					ptr = nptr
					count += 1
				if pptr is not None:
					pptr.next = prev
				else:
					head = prev
			pptr = ptr
			if h is not None:
				h.next = nptr
				break
			ptr = ptr.next
			count += 1
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		p = head
		i = 0
		while p != None and i != n:
			if i >= m - 1:
				l.append(p.data)
			i += 1
			p = p.next
		l.reverse()
		i = 0
		p = head
		while p != None and i != n:
			if i >= m - 1:
				p.data = l[i - m + 1]
			i += 1
			p = p.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		(Up, mid, end) = ([], [], [])
		p = head
		ans = 1
		while p:
			if ans < m:
				Up.append(p.data)
			if ans >= m and ans <= n:
				mid.append(p.data)
			if ans > n:
				end.append(p.data)
			ans += 1
			p = p.next
		mid = mid[::-1]
		Up.extend(mid)
		Up.extend(end)
		p1 = head = Node(Up[0])
		for i in range(1, len(Up)):
			p1.next = Node(Up[i])
			p1 = p1.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		if m == 1:
			prev = None
			curr = head
			t = curr
			for i in range(n):
				nxt = curr.next
				curr.next = prev
				prev = curr
				curr = nxt
			head = prev
			t.next = curr
			return head
		curr = head
		prev = None
		count = 0
		for i in range(m - 1):
			prev = curr
			curr = curr.next
		d = n - m
		(tmp1, tmp2) = (curr, curr)
		for i in range(d):
			tmp1 = tmp1.next
		t1nxt = tmp1.next
		tmp1.next = None
		p1 = None
		t2 = curr
		while t2:
			t2n = t2.next
			t2.next = p1
			p1 = t2
			t2 = t2n
		prev.next = p1
		tmp2.next = t1nxt
		curr = t1 = t2 = tmp1 = tmp2 = t2nxt = None
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		prv = None
		l1 = None
		for i in range(m - 1):
			if l1 == None:
				l1 = temp
			prv = temp
			temp = temp.next
		if prv:
			prv.next = None
		l2 = None
		prv = None
		for i in range(m - 1, n):
			if l2 == None:
				l2 = temp
			prv = temp
			temp = temp.next
		if prv:
			prv.next = None
		l3 = temp
		l2 = revln(l2)
		l = joinlst(l1, l2)
		l = joinlst(l, l3)
		return l

def prlst(root):
	while root:
		print(root.data)
		root = root.next

def revln(head):
	prev = None
	current = head
	while current is not None:
		next = current.next
		current.next = prev
		prev = current
		current = next
	head = prev
	return head

def joinlst(l1, l2):
	if l1:
		temp = l1
		while temp.next is not None:
			temp = temp.next
		temp.next = l2
		return l1
	else:
		return l2


class Solution:

	def reverseBetween(self, head, m, n):
		i = 1
		L = []
		n1 = head
		while n1 is not None:
			if i >= m and i <= n:
				L.append(n1.data)
			i = i + 1
			n1 = n1.next
		i = 1
		n1 = head
		while n1 is not None:
			if i >= m and i <= n:
				n1.data = L.pop()
			i = i + 1
			n1 = n1.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		cur = head
		while cur:
			l.append(cur)
			cur = cur.next
		l[m - 1:n] = l[m - 1:n][::-1]
		l.append(None)
		head = cur = l[0]
		for i in range(1, len(l)):
			cur.next = l[i]
			cur = cur.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		p = []
		a = head
		while a is not None:
			p.append(a.data)
			a = a.next
		q = p[m - 1:n]
		list3 = p[:m - 1] + q[::-1] + p[n:]
		head1 = None
		b = None
		for i in list3:
			m = Node(i)
			if head1 is None:
				head1 = m
				b = head1
			else:
				b.next = m
				b = b.next
		return head1


class Solution:

	def reverseBetween(self, head, m, n):
		a = Node(0)
		a.next = head
		b = a
		i = 1
		while i < m:
			b = b.next
			i = i + 1
		ans = b.next
		while m < n:
			x = ans.next
			ans.next = x.next
			x.next = b.next
			b.next = x
			m = m + 1
		return a.next


class Solution:

	def reverseBetween(self, head, m, n):
		a = []
		itr = head
		while itr:
			a.append(itr.data)
			itr = itr.next
		a[m - 1:n] = reversed(a[m - 1:n])
		head1 = Node(a[0])
		t = head1
		for i in range(1, len(a)):
			x = Node(a[i])
			head1.next = x
			head1 = head1.next
		return t


class Solution:

	def reverseBetween(self, head, m, n):
		ptr = head
		lst = []
		while ptr:
			lst.append(ptr.data)
			ptr = ptr.next
		x = lst[m - 1:n]
		ll = LinkedList()
		for i in range(m - 1, n):
			lst[i] = x.pop()
		for i in lst:
			ll.append(i)
		return ll.head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		k = l[:m - 1]
		r = l[m - 1:n]
		z = l[n:]
		r = r[::-1]
		l.clear()
		l.extend(k)
		l.extend(r)
		l.extend(z)
		ll = LinkedList()
		for i in l:
			ll.append(i)
		return ll.head


class Solution:

	def reverseBetween(self, head, m, n):
		arr = []
		curr = head
		while curr:
			arr.append(curr.data)
			curr = curr.next
		arr[m - 1:n] = arr[m - 1:n][::-1]
		curr = head
		for i in arr:
			curr.data = i
			curr = curr.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		first = []
		mid = []
		last = []
		p = head
		cnt = 1
		while p:
			if cnt < m:
				first.append(p.data)
			if cnt >= m and cnt <= n:
				mid.append(p.data)
			if cnt > n:
				last.append(p.data)
			cnt += 1
			p = p.next
		mid = mid[::-1]
		first.extend(mid)
		first.extend(last)
		p1 = head = Node(first[0])
		for i in range(1, len(first)):
			p1.next = Node(first[i])
			p1 = p1.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		z = []
		while head is not None:
			z.append(head.data)
			head = head.next
		z = z[:m - 1] + z[m - 1:n][::-1] + z[n:]
		h = None
		t = None
		z.append('x')
		for ele in z:
			if ele != 'x':
				newnode = Node(ele)
				if h is None:
					h = newnode
					t = newnode
				else:
					t.next = newnode
					t = newnode
		return h


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = Node(0)
		dummy.next = head
		(leftprev, curr) = (dummy, head)
		for i in range(m - 1):
			(leftprev, curr) = (curr, curr.next)
		prev = None
		for i in range(n - m + 1):
			tempnexxt = curr.next
			curr.next = prev
			prev = curr
			curr = tempnexxt
		leftprev.next.next = curr
		leftprev.next = prev
		return dummy.next


def reverse(head):
	prev = None
	curr = head
	while curr:
		next = curr.next
		curr.next = prev
		prev = curr
		curr = next
	return prev

def reverseBetween(head, m, n):
	if m == n:
		return head
	revs = None
	revs_prev = None
	revend = None
	revend_next = None
	i = 1
	curr = head
	while curr and i <= n:
		if i < m:
			revs_prev = curr
		if i == m:
			revs = curr
		if i == n:
			revend = curr
			revend_next = curr.next
		curr = curr.next
		i += 1
	revend.next = None
	revend = reverse(revs)
	if revs_prev:
		revs_prev.next = revend
	else:
		head = revend
	revs.next = revend_next
	return head

class Solution:

	def reverseBetween(self, head, m, n):
		return reverseBetween(head, m, n)


class Solution:

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		prev = None
		temp = head
		i = 1
		while i < m:
			prev = temp
			temp = temp.next
			i += 1
		rtail = temp
		rhead = None
		while i < n + 1:
			temp1 = temp.next
			temp.next = rhead
			rhead = temp
			temp = temp1
			i += 1
		if prev:
			prev.next = rhead
		else:
			head = rhead
		rtail.next = temp
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		temp = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		l2 = l[m - 1:n]
		l2.reverse()
		l[m - 1:n] = l2
		temp = head
		i = 0
		while temp:
			temp.data = l[i]
			temp = temp.next
			i += 1
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		newhead = head
		prev = None
		for i in range(m - 1):
			prev = head
			head = head.next
		last = None
		for i in range(m, n + 1):
			next = head.next
			head.next = last
			last = head
			head = next
		if prev:
			prev.next = last
		else:
			newhead = last
		while last.next:
			last = last.next
		last.next = head
		return newhead


class Solution:

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		curr = head
		prev = None
		i = 1
		while i < m:
			prev = curr
			curr = curr.next
			i += 1
		rhead = curr
		rtail = None
		while i <= n:
			next = curr.next
			curr.next = rtail
			rtail = curr
			curr = next
			i += 1
		if prev is not None:
			prev.next = rtail
		else:
			head = rtail
		rhead.next = curr
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		elements = []
		while temp is not None:
			elements.append(temp.data)
			temp = temp.next
		elements[m - 1:n] = elements[m - 1:n][::-1]
		temp = head
		i = 0
		while temp is not None:
			temp.data = elements[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		dummyNode = Node(0)
		dummyNode.next = head
		pre = dummyNode
		for i in range(m - 1):
			pre = pre.next
		reverse = None
		cur = pre.next
		for i in range(n - m + 1):
			next = cur.next
			cur.next = reverse
			reverse = cur
			cur = next
		pre.next.next = cur
		pre.next = reverse
		return dummyNode.next


class Solution:

	def reverseBetween(self, head, m, n):
		l1 = []
		l2 = []
		l3 = []
		temp = head
		count = 1
		while temp:
			if count < m:
				l1.append(temp.data)
			if count >= m and count <= n:
				l2.append(temp.data)
			if count > n:
				l3.append(temp.data)
			count += 1
			temp = temp.next
		l2 = l2[::-1]
		l1.extend(l2)
		l1.extend(l3)
		temp1 = head = Node(l1[0])
		for i in range(1, len(l1)):
			temp1.next = Node(l1[i])
			temp1 = temp1.next
		return head


class Solution:

	def printLL(self, head):
		i = 0
		while i < 10 and head:
			print(head.data, end=' ')
			head = head.next
			i += 1

	def reverseBetween(self, head, m, n):
		if n <= 1:
			return head
		i = 1
		h = head
		old = head
		while i < m and head:
			old = head
			head = head.next
			i += 1
		if head is None:
			return h
		(curr, prev, start) = (head, None, head)
		while i <= n and curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
			i += 1
		if m <= 1:
			h = prev
			start.next = curr
		else:
			start.next = curr
			old.next = prev
		return h


class Solution:

	def reverseBetween(self, head, m, n):
		res = Node(0)
		res.next = head
		temp = res
		count = 1
		while count != m:
			temp = temp.next
			count += 1
		rev = temp.next
		curr = rev
		prev = None
		for i in range(n - m + 1):
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		temp.next = prev
		rev.next = curr
		return res.next


class Solution:

	def reverseBetween(self, head, m, n):
		current = head
		i = 1
		if m == 1:
			dummy = None
			upcomming = dummy
			while current and i <= n:
				upcomming = current.next
				current.next = dummy
				dummy = current
				current = upcomming
				i += 1
			head.next = upcomming
			return dummy
		while current and i < m:
			first_half = current
			current = current.next
			i += 1
		first_half.next = None
		dummy = None
		upcomming = dummy
		while current and i <= n:
			upcomming = current.next
			current.next = dummy
			dummy = current
			current = upcomming
			i += 1
		first_half.next = dummy
		while dummy.next:
			dummy = dummy.next
		dummy.next = upcomming
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		i = min(m, n) - 1
		j = abs(m - n) + 1
		start = Node(0)
		start.next = head
		head = start
		while head and i:
			head = head.next
			i -= 1
		start_reverse = head
		head = head.next
		temp2 = None
		while head and j:
			temp1 = head.next
			head.next = temp2
			temp2 = head
			head = temp1
			j -= 1
		start_reverse.next.next = head
		start_reverse.next = temp2
		return start.next


class Solution:

	def reverseBetween(self, head, m, n):
		tek = head
		arr = []
		while tek != None:
			arr.append(tek.data)
			tek = tek.next
		i = m - 1
		j = n - 1
		while i < j:
			tmp = arr[i]
			arr[i] = arr[j]
			arr[j] = tmp
			i += 1
			j -= 1
		head1 = Node(0)
		tek = head1
		i = 0
		while i < len(arr):
			tek.next = Node(arr[i])
			tek = tek.next
			i += 1
		return head1.next


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = Node(0)
		dummy.next = head
		(leftPrev, cur) = (dummy, head)
		for i in range(m - 1):
			leftPrev = cur
			cur = cur.next
		prev = None
		for i in range(n - m + 1):
			tmpNext = cur.next
			cur.next = prev
			prev = cur
			cur = tmpNext
		leftPrev.next.next = cur
		leftPrev.next = prev
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		while head != None:
			l.append(head.data)
			head = head.next
		l[m - 1:n] = reversed(l[m - 1:n])
		a = Node(l[0])
		a.next = None
		x = a
		for i in range(1, len(l)):
			b = Node(l[i])
			b.next = a.next
			a.next = b
			a = b
		return x


class Solution:

	def reverseBetween(self, head, m, n):
		lst = []
		while head:
			lst.append(head.data)
			head = head.next
		lst = lst[:m - 1] + lst[m - 1:n][::-1] + lst[n:]
		a = Node(0)
		tmp = a
		for i in lst:
			tmp.next = Node(i)
			tmp = tmp.next
		return a.next


class Solution:

	def reverseBetween(self, head, m, n):
		arr = []
		ch = head
		while ch != None:
			arr.append(ch.data)
			ch = ch.next
		arr[m - 1:n] = arr[m - 1:n][::-1]
		ans = Node(arr[0])
		ans_c = ans
		for x in arr[1:]:
			ans_c.next = Node(x)
			ans_c = ans_c.next
		return ans


class Solution:

	def reverseBetween(self, head, m, n):
		first = None
		h = head
		pre = None
		while m > 1:
			pre = h
			h = h.next
			m -= 1
		first = h
		h = head
		second = h
		while n > 1:
			h = h.next
			n -= 1
		second = h
		post = h.next
		second.next = None
		rev = self.reverseList(first)
		if pre:
			pre.next = rev
		if post:
			first.next = post
		if not pre:
			return rev
		return head

	def reverseList(self, head):
		pre = None
		trav = head
		nhead = head
		while trav:
			ele = trav.next
			trav.next = pre
			nhead = trav
			pre = trav
			trav = ele
		return nhead


class Solution:

	def reverseBetween(self, head, m, n):
		start = None
		end = None
		count = 1
		temp = head
		(first_half, second_half) = (None, None)
		if m == 1:
			first_half = temp
			start = temp
		while temp.next:
			if count + 1 == m:
				first_half = temp
				start = temp.next
			if count == n:
				end = temp
				second_half = temp.next
				break
			count += 1
			temp = temp.next
		prev = None
		cur = start
		while cur != end:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
		if cur:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
		if start == head:
			head = prev
		else:
			first_half.next = prev
		start.next = second_half
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		start = head
		chkpt = None
		temp = None
		curr = None
		count = 0
		while head != None:
			count += 1
			if count <= n and count >= m:
				if count == m:
					tails = head
				temp = head.next
				head.next = curr
				curr = head
				head = temp
			elif count < m:
				if count == m - 1:
					chkpt = head
				head = head.next
			else:
				tails.next = head
				tails = tails.next
				head = head.next
		if chkpt:
			chkpt.next = curr
			return start
		return curr


class Solution:

	def reverse(self, node):
		prev = None
		temp = node
		while temp:
			nxt = temp.next
			temp.next = prev
			prev = temp
			temp = nxt
		return prev

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		i = 1
		node = head
		(start, start_prev, end, end_next) = (None, None, None, None)
		while node:
			if i < m:
				start_prev = node
			if i == m:
				start = node
			if i == n:
				end = node
				end_next = node.next
			node = node.next
			i += 1
		end.next = None
		end = self.reverse(start)
		if start_prev:
			start_prev.next = end
		else:
			head = end
		start.next = end_next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = Node(-1)
		dummy.next = head
		node = dummy
		for _ in range(m - 1):
			node = node.next
		pre = node.next
		cur = pre.next
		for _ in range(n - m):
			nex = cur.next
			cur.next = pre
			pre = cur
			cur = nex
		node.next.next = cur
		node.next = pre
		return dummy.next


from collections import deque

class Node:

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

class Solution:

	def addNode(self, data):
		newNode = Node(data)
		if self.head == None:
			self.head = newNode
			self.tail = newNode
		else:
			self.tail.next = newNode
			self.tail = newNode

	def __init__(self):
		self.head = None
		self.tail = None

	def reverseBetween(self, head, m, n):
		rev = deque()
		start = []
		end = []
		count = 0
		tempNode = head
		while tempNode is not None:
			count += 1
			if count >= m and count <= n:
				rev.append(tempNode.data)
			elif count < m:
				start.append(tempNode.data)
			else:
				end.append(tempNode.data)
			tempNode = tempNode.next
		for i in start:
			Solution.addNode(self, i)
		while len(rev) != 0:
			Solution.addNode(self, rev.pop())
		for i in end:
			Solution.addNode(self, i)
		return self.head


class Solution:

	def reverseBetween(self, head, m, n):
		b = []
		c = []
		tmp = head
		while tmp != None:
			b.append(tmp.data)
			if len(b) == m or len(b) > m:
				if len(b) < n + 1:
					c.append(tmp.data)
			tmp = tmp.next
		for i in reversed(c):
			b[m - 1] = i
			m += 1
		tmp = head
		for i in b:
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		j = 1
		l = []
		temp = head
		prev = None
		next = None
		while temp:
			if j >= m and j <= n:
				l.append(temp)
			elif j == m - 1:
				prev = temp
			elif j == n + 1:
				next = temp
			j += 1
			temp = temp.next
		j = -2
		while j >= -len(l):
			l[j + 1].next = l[j]
			j -= 1
		if prev:
			prev.next = l[-1]
		else:
			head = l[-1]
		l[0].next = next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		p1 = head
		p2 = head
		if m > 1:
			for i in range(m - 2):
				p1 = p1.next
		for i in range(n):
			p2 = p2.next
		prev = p2
		if m > 1:
			cur = p1.next
		else:
			cur = p1
		while cur.next != p2:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		cur.next = prev
		prev = cur
		if m > 1:
			p1.next = prev
		else:
			head = prev
		return head


class Solution:

	def reverseBetween(self, head, m, n):

		def reverseList(head):
			if head == None or head.next == None:
				return head
			prev = head
			curr = head.next
			prev.next = None
			while curr != None:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		tail1 = None
		head1 = None
		tail2 = None
		head2 = None
		count = 1
		curr = head
		if m == n:
			return head
		if m == 1:
			head1 = head
			tail = head
		else:
			while curr != None and count + 1 != m:
				curr = curr.next
				count += 1
			head1 = curr.next
			tail = curr
		while curr != None and count + 1 != n:
			curr = curr.next
			count += 1
		tail1 = curr.next
		head2 = tail1.next
		tail1.next = None
		if m == 1:
			newHead = reverseList(head1)
			head1.next = head2
			return newHead
		else:
			newHead = reverseList(head1)
			tail.next = newHead
			head1.next = head2
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		lis = []
		while head:
			lis.append(head.data)
			head = head.next
		lis[m - 1:n] = lis[m - 1:n][::-1]
		a = Node(0)
		temp = a
		for i in lis:
			temp.next = Node(i)
			temp = temp.next
		return a.next


class Solution:

	def reverseBetween(self, head, m, n):
		a = []
		b = head
		while b:
			a.append(b.data)
			b = b.next
		k = a[m - 1:n]
		a[m - 1:n] = k[::-1]
		e = w = Node(a[0])
		for i in range(1, len(a)):
			e.next = Node(a[i])
			e = e.next
		return w


class Solution:

	def reverseBetween(self, head, m, n):
		res = []
		temp = head
		while temp != None:
			res.append(temp.data)
			temp = temp.next
		res1 = []
		for i in range(m - 1, n):
			res1.append(res[i])
		res1.reverse()
		j = 0
		for i in range(m - 1, n):
			res[i] = res1[j]
			j += 1
		head1 = None
		for i in res:
			if head1 == None:
				head1 = Node(i)
				temp = head1
			else:
				temp.next = Node(i)
				temp = temp.next
		return head1


class Solution:

	def reverseBetween(self, head, m, n):
		data = []
		temp = head
		while temp:
			data.append(temp.data)
			temp = temp.next
		(first, mid, last) = (data[:m - 1], data[m - 1:n], data[n:])
		mid = mid[::-1]
		res = first + mid + last
		rBhead = Node(0)
		curr = rBhead
		for i in res:
			curr.next = Node(i)
			curr = curr.next
		return rBhead.next


class Solution:

	def reverseBetween(self, head, m, n):
		(first, mid, last) = (list(), list(), list())
		(temp, count) = (head, 1)
		while temp:
			if count < m:
				first.append(temp.data)
			if count >= m and count <= n:
				mid.append(temp.data)
			if count > n:
				last.append(temp.data)
			count += 1
			temp = temp.next
		mid = mid[::-1]
		res = first + mid + last
		rB_head = Node(0)
		curr = rB_head
		for i in res:
			curr.next = Node(i)
			curr = curr.next
		return rB_head.next


class Solution:

	def reverseBetween(self, head, m, n):
		t = head
		k = []
		while t:
			k.append(t.data)
			t = t.next
		(a, b, c) = (k[0:m - 1], k[m - 1:n], k[n:])
		b.reverse()
		a = a + b + c
		i = 0
		t = head
		while i < len(a):
			t.data = a[i]
			i += 1
			t = t.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		curr = Node(None)
		curr.next = head
		hd = curr
		for _ in range(m - 1):
			curr = curr.next
		last = curr
		start = curr.next
		curr = start
		prev = Node(None)
		for _ in range(n - m + 1):
			(curr.next, curr, prev) = (prev, curr.next, curr)
		last.next = prev
		start.next = curr
		return hd.next


class Solution:

	def reverseBetween(self, head, m, n):
		K = []
		while head:
			K.append(head.data)
			head = head.next
		K[m - 1:n] = K[m - 1:n][::-1]
		L1 = LinkedList()
		for i in K:
			L1.append(i)
		return L1.head


class Solution:

	def reverseBetween(self, head, m, n):
		f = []
		mid = []
		last = []
		c = 1
		temp = head
		while temp:
			if c < m:
				f.append(temp.data)
			if c >= m and c <= n:
				mid.append(temp.data)
			if c > n:
				last.append(temp.data)
			c = c + 1
			temp = temp.next
		mid = mid[::-1]
		f.extend(mid)
		f.extend(last)
		p = head = Node(f[0])
		for i in range(1, len(f)):
			p.next = Node(f[i])
			p = p.next
		return head


class Node:

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

class Solution:

	def reverseBetween(self, head, m, n):
		l = None
		r = None
		i = 1
		li = []
		curr = head
		while curr:
			li.append(curr.data)
			curr = curr.next
		li[m - 1:n] = li[m - 1:n][::-1]
		head = None
		tail = None
		for i in li:
			newnode = Node(i)
			if head is None:
				head = newnode
				tail = newnode
			else:
				tail.next = newnode
				tail = newnode
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		c = head
		for i in range(1, m):
			if i != m:
				c = c.next
			else:
				break
		for i in range(m, n + 1):
			l.append(c.data)
			c = c.next
		l.reverse()
		c = head
		for i in range(1, m):
			if i != m:
				c = c.next
			else:
				break
		for i in range(len(l)):
			c.data = l[i]
			c = c.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):

		def rec(nod, p):
			x = 1
			tm = nod
			while x < p and tm:
				tm = tm.next
				x += 1
			if tm:
				rs = tm.next
				tm.next = None
			else:
				rs = tm
			cur = nod
			ppr = rs
			ne = nod.next
			while cur:
				cur.next = ppr
				ppr = cur
				cur = ne
				if ne:
					ne = ne.next
			return ppr
		front = Node(0)
		front.next = head
		x = 1
		tem = front
		while x < m:
			tem = tem.next
			x += 1
		tem.next = rec(tem.next, n - m + 1)
		return front.next


def reverse_list(temp_head, count):
	cur = temp_head
	temp = None
	group_tail = None
	prev = None
	while count > 0:
		count -= 1
		temp = cur.next
		cur.next = prev
		if prev is None:
			group_tail = cur
		prev = cur
		cur = temp
	return (prev, group_tail)

def traverse_list(head, left, right):
	n = 0
	temp = head
	beg_tail = None
	end_head = None
	while temp:
		n += 1
		if n == left - 1:
			beg_tail = temp
		if n == right + 1:
			end_head = temp
		temp = temp.next
	return (n, beg_tail, end_head)

class Solution:

	def reverseBetween(self, head, m, n):
		(total, beg_tail, end_head) = traverse_list(head, m, n)
		if m > n or m < 1 or n > total or (m == n) or (total <= 1):
			return head
		new_head = None
		beg_head = head
		left_head = None
		if m == 1:
			left_head = head
		else:
			left_head = beg_tail.next
		(reversed_list_head, reversed_list_tail) = reverse_list(left_head, n - m + 1)
		if m == 1:
			new_head = reversed_list_head
		else:
			new_head = beg_head
			beg_tail.next = reversed_list_head
		if n < total:
			reversed_list_tail.next = end_head
		return new_head


class Solution:

	def reverseBetween(self, head, m, n):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		arr = arr[:m - 1] + list(reversed(arr[m - 1:n])) + arr[n:]
		h = Node(arr[0])
		p = h
		for i in range(1, len(arr)):
			h.next = Node(arr[i])
			h = h.next
		return p


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		prev = head
		v = m
		while m > 1:
			prev = temp
			temp = temp.next
			m = m - 1
		s = temp
		dummy = None
		while v <= n:
			next = temp.next
			temp.next = dummy
			dummy = temp
			temp = next
			v = v + 1
		if prev == s:
			prev.next = temp
			head = dummy
		else:
			prev.next = dummy
			s.next = temp
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = Node(-1)
		dummy.next = head
		work = dummy
		i = 0
		while work and i < m - 1:
			work = work.next
			i += 1
		if not work:
			return dummy.next
		head = work.next
		work.next = None
		tail = None
		while head and i < n:
			i += 1
			if not tail:
				tail = head
			nhead = head.next
			head.next = work.next
			work.next = head
			head = nhead
		if head:
			tail.next = head
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		first = head
		second = None
		third = None
		i = 1
		h = head
		while h:
			if i == m - 1:
				ele = h.next
				h.next = None
				i += 1
				h = ele
			if i == m:
				second = h
			if i == n:
				ele = h.next
				h.next = None
				i += 1
				h = ele
			if i == n + 1:
				third = h
			if h:
				h = h.next
			i += 1
		if first == second:
			first = None
		curr = second
		prev = None
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		if first:
			head = first
			while first.next:
				first = first.next
			first.next = prev
			while first.next:
				first = first.next
			first.next = third
			return head
		else:
			head = prev
			first = prev
			while first.next:
				first = first.next
			first.next = third
			return head


class Solution:

	def reverseBetween(self, head, m, n):

		def reverse(h1, end):
			if h1 == None:
				return
			currNode = h1
			prev = None
			while currNode != None and end > 0:
				end -= 1
				nxt = currNode.next
				currNode.next = prev
				prev = currNode
				currNode = nxt
			h1.next = currNode
			return prev
		if head == None:
			return
		dummy = Node(-1)
		newNode = dummy
		dummy.next = head
		cnt = m
		while newNode != None and cnt > 1:
			cnt -= 1
			newNode = newNode.next
		newNode.next = reverse(newNode.next, n - m + 1)
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		l = []
		while temp:
			l.append(temp.data)
			temp = temp.next
		l1 = l[m - 1:n]
		l1 = l1[::-1]
		l[m - 1:n] = l1
		ll = LinkedList()
		for i in l:
			ll.append(i)
		return ll.head


class Solution:

	def reverseBetween(self, head, m, n):
		listt = []
		count = 1
		temp = head
		while temp != None:
			if count >= m and count <= n:
				listt.append(temp.data)
			count += 1
			temp = temp.next
		temp = head
		count = 1
		num = len(listt)
		while temp != None:
			if count >= m and count <= n:
				temp.data = listt[num - 1]
				num -= 1
			count += 1
			temp = temp.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		lst = []
		curr = head
		count = 1
		while curr:
			if count >= m and count <= n:
				lst.append(curr.data)
			curr = curr.next
			count += 1
		curr = head
		count = 1
		while curr:
			if count >= m and count <= n:
				curr.data = lst[-1]
				lst.pop()
			curr = curr.next
			count += 1
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = Node(-1)
		dummy.next = head
		dprev = dummy
		curr = head
		for i in range(m - 1):
			dprev = curr
			curr = curr.next
		prev = None
		c = 0
		times = n - m + 1
		starthead = curr
		while c < times:
			t = curr.next
			curr.next = prev
			prev = curr
			curr = t
			c += 1
		dprev.next = prev
		starthead.next = curr
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		temp = head
		ar = []
		i = 0
		while temp:
			i += 1
			if i >= m and i <= n:
				ar.append(temp.data)
			temp = temp.next
		ar = ar[::-1]
		temp = head
		root = temp
		i = 0
		j = 0
		while temp:
			i += 1
			if i >= m and i <= n:
				temp.data = ar[j]
				j += 1
			temp = temp.next
		return head


class Solution:

	def reverseBetween(self, head, left, right):
		if left == right:
			return head
		dummy = Node(0)
		dummy.next = head
		prev = dummy
		i = 1
		while i < left:
			prev = prev.next
			i += 1
		cur = prev.next
		nx = cur.next
		while i < right:
			tmp = nx.next
			nx.next = cur
			cur = nx
			nx = tmp
			i += 1
		prev.next.next = nx
		prev.next = cur
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		i = 1
		j = 1
		s = head
		e = head
		if m == 1:
			while i < m:
				s = s.next
				i = i + 1
			while j < n:
				e = e.next
				j = j + 1
			t = e.next
			e.next = None
			prev = None
			current = s
			while current is not None:
				next = current.next
				current.next = prev
				prev = current
				current = next
			s.next = t
			head = e
			return head
		else:
			p = head
			while i < m:
				p = s
				s = s.next
				i = i + 1
			while j < n:
				e = e.next
				j = j + 1
			t = e.next
			e.next = None
			prev = None
			current = s
			while current is not None:
				next = current.next
				current.next = prev
				prev = current
				current = next
			s.next = t
			p.next = e
			return head


class Solution:

	def reverse(self, node):
		curr = node
		prev = None
		next = None
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev

	def reverseBetween(self, head, m, n):
		(prev, start, end, curr) = (None, None, None, head)
		i = 1
		while i <= n:
			if i == m - 1:
				prev = curr
			if i == m:
				start = curr
			if i == n:
				end = curr
			curr = curr.next
			i += 1
		lastHead = end.next
		end.next = None
		tempstart = start
		start = self.reverse(start)
		if prev:
			prev.next = start
		else:
			head = start
		tempstart.next = lastHead
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		curr = head
		previous = None
		nextev = None
		refirst = None
		relast = None
		num = 1
		while curr != None and num <= n:
			if num < m:
				previous = curr
			if num == m:
				refirst = curr
			if num == n:
				relast = curr
				nextev = curr.next
			curr = curr.next
			num += 1
		relast.next = None
		relast = self.reverse(refirst)
		if previous is not None:
			previous.next = relast
		else:
			head = relast
		refirst.next = nextev
		return head

	def reverse(self, head):
		prev = None
		current = head
		next = None
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		return prev


class Solution:

	def reverseBetween(self, head, m, n):
		stack = []
		node = head
		inx = 1
		while node is not None:
			if inx >= m and inx <= n:
				stack.append(node.data)
			inx += 1
			node = node.next
		inx = 1
		node = head
		while node is not None:
			if inx >= m and inx <= n:
				node.data = stack[-1]
				stack.pop()
			inx += 1
			node = node.next
		return head


class Solution:

	def reverseBetween(self, head, m, n):
		i = 1
		prev = None
		curr = head
		while i < m:
			prev = curr
			curr = curr.next
			i += 1
		tail = curr
		h = None
		while i <= n:
			temp = curr.next
			curr.next = h
			h = curr
			curr = temp
			i += 1
		if prev:
			prev.next = h
		else:
			head = h
		tail.next = curr
		return head


class Solution:

	def reverseBetween(self, head, m, n):

		def reverse(node):
			prev = None
			curr = node
			while curr:
				nexx = curr.next
				curr.next = prev
				prev = curr
				curr = nexx
			return prev
		curr = head
		l = 0
		while curr:
			l += 1
			if l == m:
				start = curr
			if l == n:
				second = curr.next
				curr.next = None
			curr = curr.next
		start = reverse(start)
		curr = start
		while curr.next:
			curr = curr.next
		curr.next = second
		if m == 1:
			return start
		else:
			curr = head
			l = 1
			while l < m - 1:
				l += 1
				curr = curr.next
			curr.next = start
			return head


class Solution:

	def reverseBetween(self, head, m, n):
		l = []
		while head:
			l.append(head)
			head = head.next
		c = []
		for i in range(m - 1):
			c.append(l[i])
		d = []
		for i in range(m - 1, n):
			d.append(l[i])
		d = d[::-1]
		c.extend(d)
		g = len(l)
		for i in range(n, g):
			c.append(l[i])
		for i in range(g - 1):
			c[i].next = c[i + 1]
		c[-1].next = None
		return c[0]


class Solution:

	def reverse(self, head):
		prev = None
		curr = head
		while curr:
			next_ele = curr.next
			curr.next = prev
			prev = curr
			curr = next_ele
		return prev

	def reverseBetween(self, head, m, n):
		if m == n:
			return head
		front_prev = None
		front = None
		back = None
		back_next = None
		i = 1
		curr = head
		while curr:
			if i < m:
				front_prev = curr
			if i == m:
				front = curr
			if i == n:
				back = curr
				back_next = curr.next
			curr = curr.next
			i = i + 1
		back.next = None
		reverse_head = self.reverse(front)
		if front_prev:
			front_prev.next = reverse_head
		else:
			head = reverse_head
		front.next = back_next
		return head