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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
'''

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @param {integer} m
    # @param {integer} n
    # @return {ListNode}
    def reverseBetween(self, head, m, n):
        if not head: return head
        dummy = ListNode(0)
        dummy.next = head
        head1 = dummy 
        
        for _ in xrange(m-1):
            head1 = head1.next
        p = head1.next
        
        for _ in xrange(n-m):
            tmp = head1.next
            head1.next = p.next
            p.next = p.next.next
            head1.next.next = tmp
        
        return dummy.next

f5c7efd1c1c8c53896b60227bf04a5ecc18b7730
<mask token>

<mask token>


class Solution:
    <mask token>

<mask token>


class Solution:

    def reverseBetween(self, head, m, n):
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        head1 = dummy
        for _ in xrange(m - 1):
            head1 = head1.next
        p = head1.next
        for _ in xrange(n - m):
            tmp = head1.next
            head1.next = p.next
            p.next = p.next.next
            head1.next.next = tmp
        return dummy.next

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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
'''

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @param {integer} m
    # @param {integer} n
    # @return {ListNode}
    def reverseBetween(self, head, m, n):
        if not head: return head
        dummy = ListNode(0)
        dummy.next = head
        head1 = dummy 
        
        for _ in xrange(m-1):
            head1 = head1.next
        p = head1.next
        
        for _ in xrange(n-m):
            tmp = head1.next
            head1.next = p.next
            p.next = p.next.next
            head1.next.next = tmp
        
        return dummy.next
