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

Difficulty: interview

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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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
         # print(pre.val)
         # print(end.val) if end else print("None")
         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
             # print(new_head.val) if new_head else print("none")
         return new_head


class Solution:
     def reverseBetween(self, head, m, n):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         dummy = ListNode(0)
         dummy.next = head
         pre = dummy
         
         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 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__
         
         
             
         
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """


class Solution:
     def reverseBetween(self, head, m, n):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         """
             1---->2---->3---->4---->5
            pre
                  cur
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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):
         """
         :type head: ListNode
         :type m: int
         :type n: int
         :rtype: ListNode
         """
         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