题意：
        给定链表的头节点，旋转链表，将链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。
        即，例如链表 ： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3。

方法一：
模拟

思路：
        直接模拟。
        根据题意的k值，用链表长度n - k-1,得到向右遍历的步数，可到达左部分链表的尾结点，标记为尾结点（即尾结点->next=null）;
        再将右部分链表的尾结点指向左部分链表的头结点。
        
        

class Solution {
public:
    
    ListNode* rotateLinkedList(ListNode* head, int k) {
        if(head==nullptr)
            return head;
        ListNode *p=head;
        int n=0;
        while(p){//计算链表长度
            n++;
            p=p->next;
        }
        k%=n;//取余运算
        if(k==0)
            return head;
        int cnt=n-k-1;//向右遍历的长度-1
        
        p=head;
        while(cnt--){
            p=p->next;
        }
        ListNode *q=p->next;//新的首节点
        p->next=nullptr;//尾结点结束标记
        
        ListNode *t=q;
        p=q->next;
        while(p){
            t=p;
            p=p->next;
        }
        t->next=head;//拼接链表
        return q;
    }
};

时间复杂度：
空间复杂度：

方法二：
辅助数组

思路：
        利用辅助数组存储链表旋转后的新序列，再遍历链表将新值覆盖旧值即可。

class Solution {
public:
    
    ListNode* rotateLinkedList(ListNode* head, int k) {
        if(head==nullptr)
            return head;
        ListNode *p=head;
        int n=0;
        while(p){//计算链表长度
            n++;
            p=p->next;
        }
        k%=n;//取余运算
        if(k==0)
            return head;
        int cnt=n-k;
        p=head;
        for(int i=0;i<cnt;i++){
            p=p->next;
        }
        vector<int> v;//辅助数组
        while(p){
            v.push_back(p->val);
            p=p->next;
        }
        p=head;
        for(int i=0;i<cnt;i++){
            v.push_back(p->val);
            p=p->next;
        }
        p=head;
        for(int i=0;i<n;i++){//新值覆盖旧值
            p->val=v[i];
            p=p->next;
        }
        return head;
    }
};

时间复杂度：
空间复杂度：