出處： https://leetcode.com/problems/rotate-list/submissions/
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range
[0, 500]. -100 <= Node.val <= 1000 <= k <= 2 * 109
做了一連串 Node List 的訓練之後，這種題目已經非常熟練了。這次一樣用遞迴解決。
解法如下：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
// 沒有 head 或是 head.next 直接回 head，旋轉次數為 0 時也回 head
if (!head || !head.next || k === 0) return head
// 做一個開始的 node
let node = new ListNode(-1, head)
// 設一個 fast 先到下一個 node
let fast = head.next
// 用來計算 node 的數量
// 因為已經排除了 head === null 和 head.next === null 的狀態，所以至少會有 2 個
let size = 2
// 先讓 fast 跑到最後一個 node， head 會跑到倒數第 2 個 ，一邊計算 node 的數量
while(fast.next) {
head = head.next
fast = fast.next
size++
}
// fast.next 連到開始的 node.next
fast.next = node.next
// 倒數第二個連到 null
head.next = null
// 原本的 node.next 連到 fast
node.next = fast
// 完成了一次 rotate ， 先將 k - 1 準備進入下一個遞迴
k = k - 1
// 由於 rotate 次數只要和 size 一樣，會回到原點。所以這邊取 k / size 的餘數，減少遞迴次數
if (k > size) {
k = k % size
}
// 進入遞迴
return rotateRight(node.next, k)
};
