每周一道算法题(四十六)

因为过年回家，外网一个都打不开，连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;
}

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!