61. Rotate List

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL

Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

因为要最小操作去反转list,我们需要找到最小反转步数 k%len
然后定位到 反转的节点， 将反转节点到尾部的节点 拼接在 头部即可

#include <vector>
#include <iostream>

using namespace std;

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;

        ListNode* pre = head;
        int len=0;
        while(pre!=NULL){
            pre = pre->next;
            len+=1;
        }
        int cnt = k%len;
        // k=0 直接返回
        if(cnt==0) return head;
        
        pre = head;
        ListNode* cur = head;
		// 前后节点 
        while(cur!=NULL){
            if(cnt--<0) pre = pre->next;
            cur = cur->next;
        }

        cur = pre->next;
        ListNode* tmp = cur;
        pre->next = NULL;

        for(int i=1;i< k%len ;i++){
            cur = cur->next;
            printf("%d: %d \n",i,cur->val);
        }
        cur->next = head;

        return tmp;
    }

    ListNode* Creat_list(vector<int> node) {
        ListNode* head = NULL,*tmp = NULL;

        int len = node.size();

        for(int i=0;i<len;i++){
            if (i==0){
                head = new ListNode(node[i]);
                head->next=NULL;
                tmp = head;
            }else{
                ListNode* new_op = new ListNode(node[i]);
                new_op->next = NULL;
                tmp->next = new_op;
                tmp = tmp->next;
            }

        }
        return head;
    }

};

int main() {
    vector<int> v = {1,2,3,4,5};
    ListNode *head = Solution().Creat_list(v);

    ListNode* ret = Solution().rotateRight(head,2);

    while (ret!=NULL){
        printf("%d",ret->val);
        ret = ret->next;
    }
    return 0;
}