[LeetCode] 61. Rotate List

轉自LeetCode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

<Solution>

這題用 shift 來理解會比較容易

想像這個 linkedlist 是 circular 的

那麼當 k = 2 的時候，就是往右shift 2 : 4 -> 5 -> 1 -> 2 -> 3

k = 3，就是往右 shift 3 :  3 -> 4-> 5-> 1-> 2

解題想法如下

• 先求出 list 的長度 len

• k 有可能很大，但每 shift len次，等同於沒有移動，所以先把 k = k % len

• 每次都往右 shift 1個位置

• 用 recursive 的方式重複上一個動作，直到要求的 k 次

code 如下

那剛剛有提到想像這個 linked list 是 circular 的

其實可以把這個觀念進一步延伸 (參考資料)

想法如下

• 一樣要先計算 list 的長度 len，但計算好的同時，把首尾的 node 也串起來

• 接下來，從 tail node 往前走 len - (k % len) 步，就會到 rotate 後的頭的前一個 node，然後把 head = node->next，node->next = NULL，這樣斷開就找到答案了

code 如下