首先贴出来第一遍写的AC代码,目的就是为了AC,后面从可读性、性能等方面优化。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int cnt = 0;
        ListNode* q = head,*last = head,*p = head;
        while(q)
        {
            p = q;
            q = q->next;
            cnt++;
        }
        
        if(cnt <= 1) return head;
        k%=cnt;
        if(k == 0) return head;
        cout << "cnt="<<cnt <<"k= "<<k<<endl;
        for(int i = 0;i < cnt - k -1;i++)
        {
            last = last->next;
        }
        ListNode* res = last->next;
        last->next = NULL;
        p->next = head;
        return res;
    }
};

运行结果:

Runtime: 12 ms, faster than 41.77% of C++ online submissions for Rotate List.
Memory Usage: 12.2 MB, less than 69.01% of C++ online submissions for Rotate List.

优化后的代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr)
            return head;
        
        ListNode* tail = head,*prev = head;
        int cnt = 1;
        //find the last node,count the node of List
        while(tail->next)
        {
            tail = tail->next;
            cnt++;
        }
        
        k %= cnt;
        
        if(k == 0) return head;
        
        //circle the list
        tail->next = head;
        
        //find the real tail of new list
        for(int i = 0;i < cnt - k;i++)
        {
            tail = tail->next;
        }
        
        ListNode* newhead = tail->next;
        tail->next = nullptr;
        
        return newhead;
        
    }
};

执行效率:

Runtime: 4 ms, faster than 98% of C++ online submissions for Rotate List.
Memory Usage: 12.2 MB, less than 69.01% of C++ online submissions for Rotate List.