前往
大廳
主題

LeetCode - 92. Reverse Linked List II 解題心得

Not In My Back Yard | 2021-06-15 00:00:03 | 巴幣 0 | 人氣 586

題目連結:


題目意譯:
給定一個單向連結串列(Linked List)的頭 head 以及兩個整數 left 和 right,其中 left ≦ right。將串列中位置 left 到位置 right 的節點反轉,然後回傳反轉後的串列。

限制:
串列中的節點數為 n 。
1 ≦ n ≦ 500
-500 ≦ Node.val ≦ 500
1 ≦ left ≦ right ≦ n

進階: 你可以只掃過一次便完成嗎?



範例測資:
範例 1:
輸入: head = [1,2,3,4,5], left = 2, right = 4
輸出: [1,4,3,2,5]

範例 2:
輸入: head = [5], left = 1, right = 1
輸出: [5]


解題思維:
從 head 開始數到第 left 個節點之後,仿照這題的作法即可(不過,記得我們只需反轉 left ~ right 這些節點)。

但是因為這次會從 left - 1 切開串列,所以第 left - 1 個節點需要在反轉完第 left ~ right 個節點後將 next 指向反轉後的頭(即第 right 個節點)。至於右邊的截斷點第 right + 1 因為上面那題的作法的緣故,反而不需要多作調整。

不過,可以看到當 left = 1 時,代表截斷點是在 head 前(也就是從 head 開始反轉),所以不會有前一個節點。對於這個情況要嘛特別判斷,要嘛額外宣告另一個節點作為「假的」開頭使用(Dummy)並將其作為截斷點。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作