题目链接：92

思路

思路一

思路一是比较好想到的。先找到待翻转区域最左边的元素，再找到待翻转区域最右边的元素，然后翻转该区域内的所有元素即可。这个思路的时间复杂度是O(n)，空间复杂度O(1)。

但是可以发现，虽然时间复杂度是O(n)，但如果待翻转区域足够大，实际上等同于遍历了两次链表（第一次找到左、右边界元素，第二次翻转）。有没有什么办法在一次遍历中就完成呢？

思路二：头插法。

所谓的头插法指的是，每当我遍历到待翻转区域中的一个元素时，就把它放到待翻转区域的第一个位置上（即插入到头上），这样只需要一次遍历就能够实现区域的翻转了。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 头插法
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummyHead := new(ListNode)
    dummyHead.Next = head

    preNode := dummyHead
    for i := 0; i < left - 1; i++ {
        preNode = preNode.Next
    }
    // 记录待翻转的最左边元素
    leftNode := preNode.Next
    curNode := leftNode
    // 遍历待翻转区域的每一个元素，遇到一个元素就放到该区域的头部
    for i := left; i <= right; i++ {
        nxtNode := curNode.Next
        curNode.Next = preNode.Next
        preNode.Next = curNode
        curNode = nxtNode
    }
    leftNode.Next = curNode

    return dummyHead.Next
}

时间复杂度：O(n)
空间复杂度：O(1)