61. Rotate List
题目
Given a list, rotate the list to the right by k places, where k is non-negative.
Example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
解析
题目;给定一个链表，将链表旋转到右边的k个位置，其中k是非负的。
例如:
1->2->3->4->5->NULL,为K = 2，
返还4->5->1->2->3->NULL。
/
/
分析：先遍历一遍，得出链表长度len，注意k可能会大于len，因此k%=len。
将尾结点next指针指向首节点，形成一个环，接着往后跑len-k步，从这里断开，就是结果
*/
class Solution_61 {
public:
//input:[1, 2] 3
//output:[2, 1]
ListNode *rotateRight(ListNode *head, int k) {
if (!head||k==0||!head->next)
{
return head;
}
ListNode* newHead = head;
ListNode* fast = head;
ListNode* lastNode = NULL;
int len = 0;
while (fast!=nullptr)
{
if (fast->next==NULL)
{
lastNode = fast;
}
fast = fast->next;
len++;
}
fast = head;
int step = len - k%len-1; // 注意k可能会大于len，因此k%=len
if (k%len == 0)
{
return newHead;
}
while (step)
{
step--;
fast = fast->next;
}
newHead = fast->next;
fast->next = NULL;
lastNode->next = head;
return newHead;
}
};
链接：https://www.nowcoder.com/questionTerminal/afbec6b9d4564c63b2c149ccc01c5678
来源：牛客网
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if(head==nullptr||k==0)
return head;
int len=1;
ListNode *p=head;
while(p->next){
//遍历一遍，求出链表长度
len++;
p=p->next;
}
k=len-k%len;
p->next=head;//首尾相连
for(int step=0;step<k;step++){
p=p->next;//接着往后跑
}
head=p->next;//新的首节点
p->next=nullptr;//断开环
return head;
}
};