旋转链表-灵活运用取模

题目描述：

个人题解：

        记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动 k%n 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1)−(k%n) 个节点（从 0 开始计数）。这样，我们可以先将给定的链表连接成环，然后将指定位置断开。

        具体代码中，我们首先计算出链表的长度 n，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(k%n) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。需要注意的是，当链表长度不大于 1，或者 k 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if(k == 0 || head == NULL || head->next == NULL)
        return head;
    int n = 1;
    struct ListNode* iter = head;
    while(iter->next)
    {
        iter = iter->next;
        n++;
    }
    if(k % n == 0)
        return head;
    else
    {
        iter->next = head;
        for(int i=0;i<n-k%n;i++)
        {
            iter = iter->next;
        }
    }
    struct ListNode* newhead = iter->next;
    iter->next = NULL;
    return newhead;
}

复杂度分析：

时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。

空间复杂度：O(1)，我们只需要常数的空间存储若干变量。