力扣 61 旋转链表
题目描述
给你一个链表的头节点 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 <= 1000 <= k <= 2 * 109
思路分析
最开始的时候我是尝试过截断法的，就是每旋转一次，就将后面的结点指向头结点并把前面的结点的指针截断置空，但后面调试发现，这只适用于旋转一次，因为旋转后，新的尾结点的前驱结点找不到了，就算实现了，时间复杂度O（n2）也挺高的。
后面我发现了一种思路，也是截断法，但不同的在于它是一次性截完，我们之前写过一题，找出链表的倒数第N个结点，比如说n=2，当我们找到了倒数第二个结点时，我们发现，该节点后面的所有结点不就是我们所需要旋转的结点吗，我们就没必要一个个截断，找到所有需要旋转的点一次性截断就行了。
关于快慢指针走的步数，题目给的值万一很大就会超出时间限制，其实我们之前写过关于字符串的旋转，当旋转次数等于字符串长度时，等于没旋转，记得将次数模一下链表长度再进循环。
代码语言：javascript复制/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
struct ListNode* tail=head;//快指针
struct ListNode* prev=head;//慢指针
struct ListNode* cur=head;//记录链表长度
int n=0;
if(k==0||head==NULL||head->next==NULL)
{
return head;
}
while(cur)
{
n ;
cur=cur->next;//计算链表长度
}
k=k%n;//记得模一下
//找需要截断的结点位置
while(k--)
{
if(tail->next==NULL)
{
tail=head;
}
else
{
tail=tail->next;
}
}
while(tail->next)
{
tail=tail->next;
prev=prev->next;
}
//截断
tail->next=head;//将末尾结点指向头结点
head=prev->next;//头结点移动到prev的下一个成为新头节点
prev->next=NULL;//截断prev和tail，prev成为链表尾结点
return head;
}
