LeetCode]—Rotate List 循环右移链表
Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL
and k = 2
,
return 4->5->1->2->3->NULL
.
题意要求循环右移链表,那就先把链表结成环。循环右移就变为了找到新的head,和tail ,并将tail->next 设为NULL。其实tail就是head的前一个节点。
注意:有可能k大于n。当k大于n时链表可能就循环右移了几圈了。所以求k%n。
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
ListNode *tail=head;
int n=1; //n表示节点数
if(head==NULL || head->next==NULL) return head;
while(tail->next!=NULL){
tail=tail->next;
n++;
}
//结成环
tail->next=head;
k=k%n; //防止k大于n
int count=n-k-1; //少前进一步,为了先找到head的前一个节点tail。
tail=head;
while(count!=0){
tail=tail->next;
count--;
}
head=tail->next; //head 就是tail的下一个节点
tail->next=NULL;
return head;
}
};