因为过年回家，外网一个都打不开，连GitHub都上不去，所以也就一直没写算法题，后来因为航班取消，导致三月份才回来上班，这运气也是没谁了。。。本周题目难度级别'Medium'，使用语言'C'
题目：把一个链表右旋k个值。eg:把1->2->3->4->5->NULL转2个数就变成4->5->1->2->3->NULL，转3个数就是3->4->5->1->2->NULL
思路：我做这题的思路是先看下这个链表有多少个节点，然后找到需要旋转的位置，作为返回链表的头部，最后把头部前面的节点接到最后就行，下面看看代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (head == NULL || k == 0) return head;
//计算链表节点个数
struct ListNode *temp = head;
int length = 1;
while(temp->next) {
temp = temp->next;
length++;
}
//move是移动的位置
int move = length - k;
if (move == 0 || length == 1 || (k % length) == 0) return head;
while(move < 1) {
k -= length;
move = length - k;
}
//移动到新的头部
temp = head;
for (int i = 0; i < move; i++) temp = temp->next;
struct ListNode *result = temp;
//将新头部前面的节点接到链表最后
for (int i = 0; i < (k-1); i++) temp = temp->next;
temp->next = head;
//断开新的头部节点
for (int i=0; i <= length - k - 1; i++) temp=temp->next;
temp->next = NULL;
return result;
}
虽然通过了测试(尽然没有超时)，但效率low到爆，看那么多for循环就知道了，其实我开始不是那么做的，我前面是算出位移大小int bit = sizeof(struct ListNode) / sizeof(head);，然后通过偏移来完成
struct ListNode *result = head + bit * move;
(result + bit * (move - 1))->next = head;
(head + bit * (length - move - 1))->next = NULL;
Run的时候没问题，但是提交的时候就提示我result的内存被释放了两次，因为链表的内存地址不是连续的，所以跑起来有可能就会偏移到别的地方去，然后我才傻了吧唧的用For去寻找位置，其实我们之前做过一道算法题是删除链表的倒数第K个节点，可以通过那个方式去做这个题，效率会高一些，最近比较忙，就先上这个比较low的答案吧
按之前的思路重写了下代码，效率不可同日而语，基本上是最优解了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (!head || k == 0) return head;
//计算链表节点个数
struct ListNode *fast = head, *slow = head;
int length = 1;
while(fast->next) {
fast = fast->next;
length++;
}
k %= length;
if (k == 0 || length == 1) return head;
fast = head;
for (int i = 0; i < k; i++) fast = fast->next;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
fast->next = head;
head = slow->next;
slow->next = NULL;
return head;
}
