分析

• 本题的考点：链表。

• 假设链表的长度为n，则链表旋转n的倍数等于没旋转，因此首先要让k对n取余，即k %= n。

• 然后如果此时$k \neq 0$的话，直接将后k个节点移到最前面即可，如下图：

代码

• C++

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {

        if (k == 0 || !head) return head;

        int n = 0;
        ListNode* tail;
        for (auto p = head; p; p = p->next) {
            tail = p;
            n++;
        }
        k %= n;
        if (!k) return head;

        auto p = head;
        for (int i = 0; i < n - k - 1; i++) p = p->next;
        tail->next = head;
        head = p->next;
        p->next = NULL;

        return head;
    }
};

• Java

class Solution {
    public ListNode rotateRight(ListNode head, int k) {

        if (k == 0 || head == null) return head;

        int n = 0;
        ListNode tail = head;
        for (ListNode p = head; p != null; p = p.next) {
            tail = p;
            n++;
        }
        k %= n;
        if (k == 0) return head;

        ListNode p = head;
        for (int i = 0; i < n - k - 1; i++) p = p.next;
        tail.next = head;
        head = p.next;
        p.next = null;

        return head;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(1)$。