给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
输入:head = [0,1,2], k = 4
输出:[2,0,1]
提示:
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
这个题目有个错误的解法:就是利用快慢指针将要倒数k个数值截取放到前面,但是k有可能大于总元素的长度
正确的解法是将链表变成环形链表然后,然后计算最后的数值在链表中的位置,k%链表长度为一个链表中需要移动的次数,所以要从链表尾部k%链表长长度值处将环形链表切开。
public ListNode rotateRight(ListNode head, int k) {
if(head==null)
return head;
ListNode cur=head;
int count=1;
while (cur.next!=null)
{
cur=cur.next;
count++;
}
cur.next=head;
int n=count-k%count;
cur=head;
for(int i=0;i<n-1;i++)
{
cur=cur.next;
}
head=cur.next;
cur.next=null;
return head;
}