前往
大廳
主題

LeetCode - 61. Rotate List 解題心得

Not In My Back Yard | 2020-11-23 00:00:01 | 巴幣 0 | 人氣 230

題目連結:


題目意譯:
給定一個連結串列(Linked List)的頭,向右旋轉該串列 k 個位置。

限制:
串列的節點數位於 [0, 500] 範圍中。
-100 ≦ Node.val ≦ 100
0 ≦ k ≦ 2 × 10 ^ 9



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

範例 2:
輸入: head = [0,1,2] , k = 4
輸出: [2,0,1]


解題思維:
先掃過一次連結串列,統計其長度 L 並找到其最後一個節點。

可以看到向右旋轉每做 L 次,就會回到原本的串列之狀態。因此,做 k 次向右旋轉等同於只做了 M = k % L 次(「%」代表取餘數,因此 M 值介於 0 ~ L - 1 之間)。

並且可以看到如果做了 M 次,則新串列的結尾會是原本的倒數第 M + 1 個節點、而新的頭即是該節點原本指向的下一個節點。

當然,當 M = 0 時,代表新結尾還是原本那個,所以不用做任何動作;當 M ≧ 1 時,我們可以找到倒數第 M + 1 個節點 A,然後將原本的結尾之下一個節點指向原本的頭,然後令指向頭的指標設為 A 的下一個節點並將 A 的下一個節點改為指向空(Null)。這樣便將串列往右旋轉了 k 次。

最後根據題目要求回傳新的頭即可。




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

創作回應

更多創作