Rotate List

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 <= 100
0 <= k <= 2 * 10<sup>9</sup>

アプローチ

思考

k 回分 linked list をローテーションする
末尾のノードを削除する
末尾まで pointer を動かし、k 回分削除を繰り返す（dubly linked list ではないため、後ろに戻れない）
削除したノードを append する
- 全ての val を取り出して、並べ替えて linked list を再生成すれば解答できるが、これは本問題の意図ではないと考える

実装

class Solution:  
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:  
        cur, prev = head, None  
        deleted_node = []  
  
        while cur:  
            prev, cur = cur, cur.next  
  
        for _ in range(k):  
            deleted_node.append(prev.val)

Time Space