61. 旋转链表

https://leetcode-cn.com/problems/rotate-list/

解法一：

头插法执行k轮，后来发现k可能特别大，观察发现若链表长度为L，操作L轮即得到原链，因此可以用k%L轮操作即可。

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next:  #边界条件
            return head
        i = head
        length = 0
        while i:
            i = i.next
            length += 1  #求链长
        k = k % length  #跳过重复周期
        for _ in range(k):    #k轮头插法
            i, j = head, head.next.next  #i为要移动结点的前驱，j指向i后两位
            while j:
                i = i.next
                j = j.next
            #头插
            i.next.next = head
            head = i.next
            i.next = j
        return head

解法二：

将末尾的长度为k的链段整体平移到头部，比解法一稍微快些

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return head
        n = 0
        i = head
        while i:
            n += 1
            i = i.next
        k = k % n   #排除重复循环
        Head = ListNode(0)
        Head.next = head
        i = Head
        #找要平移的链段前驱
        for _ in range(n-k):
            i = i.next
        pre = i
        #找平移链段末尾
        for _ in range(k):
            i = i.next
        end = i
        #整体插入
        end.next = Head.next
        Head.next = pre.next
        pre.next = None
        return Head.next