題目鏈接：92

思路

思路一

思路一是比較好想到的。先找到待翻轉(zhuǎn)區(qū)域最左邊的元素，再找到待翻轉(zhuǎn)區(qū)域最右邊的元素，然后翻轉(zhuǎn)該區(qū)域內(nèi)的所有元素即可。這個(gè)思路的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度O(1)。

但是可以發(fā)現(xiàn)，雖然時(shí)間復(fù)雜度是O(n)，但如果待翻轉(zhuǎn)區(qū)域足夠大，實(shí)際上等同于遍歷了兩次鏈表（第一次找到左、右邊界元素，第二次翻轉(zhuǎn)）。有沒(méi)有什么辦法在一次遍歷中就完成呢？

思路二：頭插法。

所謂的頭插法指的是，每當(dāng)我遍歷到待翻轉(zhuǎn)區(qū)域中的一個(gè)元素時(shí)，就把它放到待翻轉(zhuǎn)區(qū)域的第一個(gè)位置上（即插入到頭上），這樣只需要一次遍歷就能夠?qū)崿F(xiàn)區(qū)域的翻轉(zhuǎ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
    }
    // 記錄待翻轉(zhuǎn)的最左邊元素
    leftNode := preNode.Next
    curNode := leftNode
    // 遍歷待翻轉(zhuǎn)區(qū)域的每一個(gè)元素，遇到一個(gè)元素就放到該區(qū)域的頭部
    for i := left; i <= right; i++ {
        nxtNode := curNode.Next
        curNode.Next = preNode.Next
        preNode.Next = curNode
        curNode = nxtNode
    }
    leftNode.Next = curNode

    return dummyHead.Next
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)