给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

---

解题思路：本题中比较简单想法就是使用递归做法，每做一次递归使得k-1，将尾节点接到首节点左边，但是这样做当K特别大时会出现栈溢出的情况。
其实像例1中，链表长度length为5，当k为5，10，15时，链表其实是没有变化的，当k为6，11，16时也只是相当于旋转了一次，所以旋转得次数其实是k%length。此时可以使用上面的递归解法。代码如下所示：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null||head.next==null) return head;int length=1;ListNode temp=head;while(temp.next!=null){length++;temp=temp.next;}k=k%length;return  rotateNode(head,k);}public ListNode rotateNode(ListNode head,int k){if(k==0) return head;ListNode temp=head;while(head.next.next!=null){head=head.next;}//right_node为尾节点ListNode right_node=head.next;//断开链接head.next=null;right_node.next=temp;head=right_node;return rotateRight(head,k-1);}
}

不过这个算法的时间复杂度偏高，在已经知道了旋转几次的前提下，其实可以直接将链表一分为二，然后调换顺序进行拼接
比如在例子1中，k等于2，那么就相当于将4->5拆分，然后拼接到头节点上即可。此时时间复杂度只有O(1);代码如下所示：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(k==0||head==null||head.next==null){return head;}int n=1;ListNode cur=head;while(cur.next!=null){cur=cur.next;n++;}cur.next=head;int last=n-k%n;ListNode la=head;for(int i=1;i<last;i++){la=la.next;}head=la.next;la.next=null;return head;}
}