Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:


Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        

Solutions:
class Solution:

	def reverseBetween(self, head, m, n):
		if head is None or head.__next__ is None or m == n:
			return head
		h = ListNode(-1)
		h.next = head
		fast = slow = h
		for _ in range(n - m + 1):
			fast = fast.__next__
		for _ in range(m - 1):
			fast = fast.__next__
			slow = slow.__next__
		prev = fast.__next__
		curr = slow.__next__
		while prev != fast:
			temp = curr.__next__
			curr.next = prev
			prev = curr
			curr = temp
		slow.next = prev
		return h.__next__


class Solution:

	def reverseBetween(self, head, m, n):
		pre = dummy = ListNode(0)
		dummy.next = head
		num = 0
		first = last = ListNode(0)
		while head:
			num += 1
			if num == m:
				preFirst = pre
				first = head
			if num == n:
				last = head
				laLast = last.__next__
				break
			head = head.__next__
			pre = pre.__next__
		while first != last:
			pre = first
			preFirst.next = pre.__next__
			pre.next = last.__next__
			last.next = pre
			first = preFirst.__next__
		return dummy.__next__


class Solution:

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

		def reverse(head, m, n):
			m_node = head.__next__
			current = m_node.__next__
			prev_node = m_node
			position2 = m + 1
			while position2 <= n:
				next_node = current.__next__
				current.next = prev_node
				prev_node = current
				current = next_node
				position2 += 1
			m_node.next = next_node
			return prev_node
		if m == n:
			return head
		sentinal = ListNode(-1)
		sentinal.next = head
		current = sentinal
		position = 0
		while current.__next__ is not None:
			if position + 1 == m:
				pre_m = current
				pre_m.next = reverse(pre_m, m, n)
				break
			else:
				position += 1
				current = current.__next__
		if position == 0:
			return pre_m.__next__
		else:
			return head


class Solution:

	def reverseBetween(self, head, m, n):
		if n == 1:
			return head
		sentinel = ListNode(0)
		pre = sentinel
		pre.next = head
		end = head
		while m > 1:
			pre = pre.__next__
			m -= 1
		while n:
			end = end.__next__
			n -= 1
		new_start = self.reverse(pre.__next__, end)
		pre.next = new_start
		return sentinel.__next__

	def reverse(self, cur, end):
		new_head = end
		while cur != end:
			next = cur.__next__
			cur.next = new_head
			new_head = cur
			cur = next
		return new_head


class Solution:

	def reverseBetween(self, head, m, n):
		dummy = ListNode(-1)
		dummy.next = head
		count = 0
		pre = dummy
		while head:
			count += 1
			temp = head.next
			if count == m:
				mNode = head
			if count < m:
				pre = pre.next
			if count > m and count <= n:
				head.next = pre.next
				pre.next = head
				mNode.next = temp
			head = temp
		return dummy.next


class Solution:

	def reverseBetween(self, head, m, n):
		dummyNode = ListNode(0)
		dummyNode.next = head
		pre = dummyNode
		for i in range(m - 1):
			pre = pre.__next__
		cur = pre.__next__
		reverse = None
		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):
		if n == m:
			return head
		pre_head = head
		re_tail = head
		for i in range(m - 1):
			pre_head = re_tail
			re_tail = pre_head.__next__
		tmp_head = re_tail
		new_head = None
		for i in range(n - m + 1):
			next_node = tmp_head.__next__
			tmp_head.next = new_head
			new_head = tmp_head
			tmp_head = next_node
		re_tail.next = tmp_head
		if m == 1:
			return new_head
		else:
			pre_head.next = new_head
			return head


class Solution:

	def reverseBetween(self, head, m, n):
		if not head:
			return None
		node = ListNode(0)
		node.next = head
		pre = node
		cur = node.__next__
		for i in range(m - 1):
			pre = pre.__next__
			cur = cur.__next__
		for i in range(n - m):
			tmp = cur.__next__
			cur.next = tmp.__next__
			tmp.next = pre.__next__
			pre.next = tmp
		return node.__next__


class Solution:

	def reverseBetween(self, head, m, n):
		h = ListNode(0)
		h.next = head
		count = 0
		cur = h
		leftPrev = None
		prev = None
		right = None
		while cur:
			if count == m:
				leftPrev = prev
				left = cur
			if count == n:
				right = cur
				break
			count += 1
			prev = cur
			cur = cur.__next__
		if leftPrev == None or left == right:
			return h.__next__
		rightNext = right.__next__
		tail = right.__next__
		cur = left
		while cur != rightNext:
			temp = cur
			cur = cur.__next__
			temp.next = tail
			tail = temp
		leftPrev.next = tail
		return h.__next__


class Solution:

	def reverseBetween(self, head, m, n):
		if m == 1:
			m_node = head
		else:
			m_pre = head
			for i in range(m - 2):
				m_pre = m_pre.next
			m_node = m_pre.next
		a = m_node
		b = a.next
		c = a.next
		a.next = None
		for i in range(n - m):
			c = c.next
			b.next = a
			a = b
			b = c
		m_node.next = c
		if m == 1:
			return a
		else:
			m_pre.next = a
			return head