Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1 Output: [5]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
SOL：
原本想用暴力法取出需要reverse的那一段後，用之前寫過的Reverse Linked List把它reverse之後，在接起來就好了。
但實際把reverse寫成一個function後，發現reverse過後linked list的會把原本題目給的head打亂。
異於array只要另外copy就好，linked list無法copy資料，只能把記下指標。
所以參考別人的解法：Reverse Linked List II | In-place Reversal of a LinkedList 基礎概念 2 - Python - LeetCode 92
大概的解題思路如下：
首先使用cur來拜訪 linked list，並且需要prev來記錄cur的上一個node。
Part1是從head到left之前，Part2是從left到right需要被reverse的這一段。
當cur拜訪到第left個(part2StartNode)、prev是left-1個(part1LastNode)時，需要額外記錄，因為part1LastNode之後會接到reversed linked list的頭，而part2StartNode會接之後的尾巴。
拜訪完前left個，當我們開始處理Part2的時候，就可以使用之前寫過的Reverse Linked List把它reverse。
我們透過 right-left+1可以計算出需要被reverse的node有幾個。
程式碼如下：
第一個小提醒是 prev 記得先宣告，不然left=1的時候，prev會沒有被宣告到。
然後記下part1LastNode、part2StartNode還有後續的接來接去需要想一下。
留言列表
烘焙 (2)
