leetcode: 92. Reverse Linked List II

# 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.

class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution():
    def reverseBetween(self, head, m, n):
        if head == None or head.next == None:
            return head
        dummy = ListNode(0); dummy.next = head
        p = dummy
        for i in range(m - 1):
            p = p.next
        q = p.next
        for i in range(n - m):
            tmp = p.next
            p.next = q.next
            q.next = q.next.next
            p.next.next = tmp
        return dummy.next


if __name__ == "__main__":
    head, head.next, head.next.next, head.next.next.next, head.next.next.next.next \
        = ListNode(1), ListNode(2), ListNode(3), ListNode(4), ListNode(5)
    print(Solution().reverseBetween(head, 2, 4))