描述

给定链表的头节点，旋转链表，降链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。
即，例如链表 ： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3
数据范围：链表中节点数满足  ， 
问题分析：循环移位，其实跟数租循环移位差不多，只不过数组可以直接获得数租长度，而链表长度未知。所以需要先
遍历一遍链表获得链表长度num，不能先操作，因为k可能比链表长度大。然后用k对num取余，结果肯定比链表长度小。
然后让两个指针同时指向head，先让一个指针走k步（也可以一步一步走k步），这里还是采用每次走两步，走k/2步，
只不过需要判断k是奇数还是偶数。是奇数时，走完k/2步后再向后走一步，然后两个指针同步走，直到快指针的下一个指向
nullptr（注意快指针不能走到nullptr），因为对链表的操作是需要让快指针指向头节点的，然后让头节点指向慢指针的
下一个作为新表头。最后还需要让慢指针的下一个指向nullptr，不然就是一个循环链表。
具体过程看下面代码，有详细注释。
复杂度分析：
时间复杂度O(n)：先找链表尾部O(n/2)，第二次遍历O(n)。
空间复杂度O(1)：只定义了两个指针变量和一个int变量。 

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* rotateLinkedList(ListNode* head, int k) {
        // write code here
        if(head==nullptr||head->next==nullptr||0==k) return head;
        ListNode *tmp=head,*tmp2;
        int num=0;
        //利用指针每次走两步，快速定位到结尾
        while(tmp->next!=nullptr&&tmp!=nullptr) tmp=tmp->next->next,++num;
        if(tmp==nullptr) num=2*num;
        else num=2*num+1;
        k%=num;//k可能大于num，所以需要先取余
        if(k==0) return head;//k%num==0,说明移动链表总长度的倍数相当于没移动
        tmp=head,tmp2=head;
        if(!(k&1)) {//k是偶数,直接让tem每次走两步，走k/2步就到了第k个了。
            k/=2;
            while(k>0) tmp=tmp->next->next,--k;
        }
        else {//k是奇数，tmp每次走两步，走k/2步后再走一步就到第k个了
            k/=2;
            while(k>0) tmp=tmp->next->next,--k;
            tmp=tmp->next;
        }
        //然后每次两个都只走一步，直到前面的到达null，然后直接修改指针指向
        while(tmp->next!=nullptr) tmp=tmp->next,tmp2=tmp2->next;
        tmp->next=head;//将尾节点指向头节点
        head=tmp2->next;//将头指针指向慢走的下一个作为新表头
        tmp2->next=nullptr;//将慢指针的下一个指向nullptr
        return head;
    }
};