# LeetCode Medium 61. Rotate List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢単方向連結リストを右向きにkだけ回転させろ｣という問題です．

解法

• 先頭のノードへのポインタを2つ作ります．(1つはノードの数を数え，最後のノードを先頭に繋げるp，1つは位置をずらす際に使うp)
• ノードを最後まで探索して，探索したノードの数を数えます．
• こうして，探索し終わったノードを先頭のノードに繋げます．
• そして，cnt - k - 1回(kはcntで割ったあまり)qを次のポインタのノードにします．
• こうすることで，qを先頭にしたいノードの前のノードにすることができ，qの次のノードを答えにし，qの次のポインタをNULLにすることで，連結リストを循環しないようにすることが出来ます．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        p = q = head
        cnt = 1
        while p.next:
            p = p.next
            cnt += 1
        p.next = head
        k %= cnt
        for _ in range(cnt-k-1):
            q = q.next
        ans = q.next
        q.next = None
        return ans