Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

給定Singly Linked List(單鏈表)的頭節點，以及兩個整數 left 和 right，left <= right，請反轉
Singly Linked List(單鏈表)中在 left 及 right 之間範圍內的所有nodes(節點)後，回傳此Singly Linked List(單鏈表)。

這是昨天的進階題，反轉的過程是相同的，只是多了一個條件—— 指定要反轉指針的範圍。

以上面題目提供的Example 1為例，如下圖，先把left指向null，並反轉left與right之間的指針後，再把1指向4、2指向5(就是把剩下的頭尾也接起來)，便完成整個linked list的部分反轉。

步驟

1. 先排除兩種情況: linked list為空 或是 不須反轉linked list。如果是，那麼就直接回傳頭節點。
2. 新增一個虛擬節點dummy，讓dummy指向head，這樣一來，原本head的頭節點就變成了一般節點，dummy則成為了head的新頭節點。

這麼做是為了處理當left = 1時的特殊情況，因為當left = 1時進行反轉鏈表，有了dummy這個新的頭節點，當left = 1 時，進行指針反轉，我們就可以透過dummy找到原本的head節點了。

3. 利用for loop把要開始反轉的節點位置(也就是left對應的節點)找出來
4. 找到left對應的節點後，開始進行反轉。這邊反轉的步驟就跟昨天的Reverse Linked List一樣，current就是要準備反轉的第一個節點
5. 利用for loop把left到right之間的節點進行反轉
   5-1. 暫存 current 節點的下一個節點（準備要插入到頭節點的節點）

// 以下以 left = 2, right = 4 作為範例，圖解每一次for loop會執行的步驟
> tempNext = current.next
prev     curr   tempNext
  1  -->  2  -->   3  -->  4  -->  5

5-2. 將 current 的下一個指針跳過 tempNext 節點，指向 tempNext 的下一個節點

> current.next = tempNext.next
prev     curr   tempNext
  1  -->  2  -x->   3  -->  4  -->  5     (2指向4)
           ＼＿＿＿＿＿＿＿↗                           

5-3. 將 tempNext 插入到反轉鏈表的頭部，它指向當前 prev 的下一個節點

> tempNext.next = prev.next
prev     curr   tempNext
  1  -->  2  <--   3  -->  4  -->  5    (3指向2)
           ＼＿＿＿＿＿＿↗                           

5-4. 更新 prev 的指针，使其指向新的頭節點 next，即反轉後的鏈表頭部

> prev.next = tempNext
prev     curr   tempNext
   ／￣￣￣￣￣￣￣↘
  1  -x->  2  <--   3  -->  4  -->  5    (1指向3)
           ＼＿＿＿＿＿＿↗          
                   ↓ 等同於下面
                   ↓
   1  -->  3  -->  2  -->  4  -->  5                

6. 完成for loop重複執行上面步驟後，回傳結果

程式碼

function reverseBetween(head, left, right) {
  if (!head || left === right) return head; 

  let dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  for (let i = 1; i < left; i++) {
    prev = prev.next;
  }

  let current = prev.next; //left位置的節點
  let next = null; 

  // 反轉left和right中間的節點
  for (let i = 0; i < right - left; i++) {
    tempNext = current.next; //暫存 current 節點的下一個節點（準備要插入到頭節點的節點）
    current.next = tempNext.next;//將 current 的下一個指針跳過 next 節點，指向 next 的下一個節點
    tempNext.next = prev.next;// 將 next 插入到反轉鏈表的頭部，它指向當前 prev 的下一個節點
    prev.next = tempNext;//更新 prev 的指针，使其指向新的頭節點 next，即反轉後的鏈表頭部
  }

  return dummy.next;//指向新鏈表的頭節點
}

賽後感想
原本開賽前計畫可以每篇都是圖文並茂，畢竟圖解勝過文字，不過發現比賽規則有至少300字的限制，再加上比賽中期被追趕的狀態，只能先用文字表達，真的假日有空閒才補上幾張圖，這大概這次美中不足的地方，話雖如此，這次還是慶幸有參加，原本只是抱持著好奇的心態參加(我就問每天一篇能幹嘛)，後來發現這是一個逼自己精進的過程，凡走過都是屬於我自己的痕跡，這就是收穫啊!