Problem
leetcode链接problem
题目实际上是一个链表操作,在链表操作的基础上,我们对他添加一些优化即可。
Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL || head->next == NULL)
{
return head;//处理不需要旋转的情况
}
int length = 0;
ListNode* temp = head;
length = 1;
while(temp->next != NULL)//计算链表的长度
{
length++;
temp= temp->next;
}
k = k % length;//如果旋转次数大于链表长度实际上是没有必要的旋转,因此,这个部分不需要考虑,直接取余就可,这里可大大减少次数。
for(int i = 0;i < k;i++)//需要执行k次循环
{
ListNode* p = head;
ListNode* pre = head;
p=p->next;
while(p->next != NULL)//把指针移到最后。嘻嘻嘻
{
pre = pre->next;
p = p->next;
}
pre->next = NULL;
p->next = head;
head = p;
}
return head;
}
};