b. 92. Reverse Linked List II (Medium)

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

1. 思路

a. 创建dummy节点的目的是让边界情况能像非边界情况一样方便处理。（如果m=1，mnode就是第一个节点，此时如果没有dummy节点那么pre节点就为空。 b. 通过设定的i递增找到pre节点，m节点，n节点 c. 找到相应的节点之后就是整个算法的核心：当mnode和nnode没有重合之前，将mnode移到nnode后面，然后令mnode为之前mnode的下一个节点 d. 当mnode和nnode重合时，对应部分的链表就翻转成功了

2. 代码

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        mnode = head
        nnode = head
        pre = dummy
        i = 1
        while i <= n:
            if i < m:
                mnode = mnode.next
                pre = pre.next
            if i < n:
                nnode = nnode.next
            i += 1
        while(mnode != nnode):
            pre.next = mnode.next
            mnode.next = nnode.next
            nnode.next = mnode
            mnode = pre.next
            mnode = pre.next
        return dummy.next