###### tags: `Leetcode` `medium` `list` `python`

# 61. Rotate List

## [題目連結:] https://leetcode.com/problems/rotate-list/

## 題目:
Given the ```head``` of a linked list, rotate the list to the right by ```k``` places.



#### [圖片來源:]https://leetcode.com/problems/rotate-list/

## 解題想法:
* 題目要求可視為每次將尾的node移到head，執行k次
* 將head與tail串聯起來成一個cycle
* 如何求正確斷的位置:
* 計算list總node數:num
* **num - (k % num )** 為最終正確的起始位置
* 但是要斷掉cycle，所以要取(num-k%num)前一個位置

* 示意圖:

## Python:

class ListNode(object):
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def print(self):
        head = self
        array = []
        while head:
            array.append(head.val)
            head=head.next
        print(array)

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        tail=head
        #計算list長度
        num=0
        while tail.next:
            num+=1
            tail=tail.next
        num+=1 #因為while判斷是next，會少加1個
        #連成cycle
        tail.next=head
        #將尾短在正確位置
        #因為num-(k%num)可以得到最終的起始head
        #但是要斷cycle，所以要取(num-k%num)前一個位置
        cut=head
        for _ in range(num-(k%num)-1):
            cut=cut.next
        res=cut.next #最終起始head
        cut.next=None #斷cycle
        return res


if __name__ == '__main__':
    head = ListNode(1)
    head.insert(2)
    head.insert(3)
    head.insert(4)
    head.insert(5)
    head.print()
    k=2
    result = Solution()
    ans = result.rotateRight(head,k)
    ans.print()

''' 
想法:
    1 2 3 4 5 
    鏈表長度是n=5 要轉K=2
則: 需要求新的頭位置
因為k有可能>n : 要先 k%n
新起點為 n倒數k個位置: n-(k%n) = 3 所以位置在3(值為4)
要斷掉前面一個的鎖鏈: 所以為n-(k%n)-1
'''