题目描述
给你一个链表的头节点 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
解题思路
特判：如果链表为空，直接返回空。
接下来
1.用num记录链表中元素的个数，并且计数到最后一位的时候让链表闭环，首尾相连，并且退出计数循环。
2.因为k是向右移动的位置，所以我们用resNum来记录num-k%num的值，这个表达式算出来的就是移动完之后链表头结点所处的位置。
3.从头结点开始，i=1，进入循环，i要小于resNum+1，用pre记录前一个结点，p记录当前结点。
当退出循环的时候，i=resNum+1，即新的头结点位置
因为当前链表还是一个闭环的，所以此时p前面的结点pre其实就是新链表的最后一个结点，我们直接让pre->next=NULL就完成了断开闭环，称为链表的功能。
4.最后返回新的头结点p即可。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==NULL){//特判：如果链表为空，直接返回空
return NULL;
}
int num=0; //用来记录链表里面元素的个数
ListNode* p=head;//移动指针
while(true){
num++;//因为前面把链表为空的情况特判了，所以这边第一次进循环可以直接++
if(p->next==NULL){//如果当前结点的下一个结点为空结点
p->next=head;//就让他闭环
break;//并且退出虚幻
}
p=p->next;//否则的话就让p后移
}
p=head;//移动指针p重新指向头
int resNum=num-k%num;//这个是往右移动k位之后，新的头结点所处的位置
ListNode* pre=p;//新的头节点的直接前驱
for(int i=1;i<1+resNum;i++){//这个循环退出的时候正好p就是新的头节点
pre=p;//记录直接前驱
p=p->next;//p后移
}
pre->next=NULL;//将前驱结点的直接后继变为NULL之后可以完成把闭环解开成为单链表的功能
return p;//返回当前新的头节点
}
};
|