题目

Given the head of a linked list, rotate the list to the right by k places.

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Input: head = [1], k = 0
Output: [1]

Constraints:
The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109

思路

快慢指针

• 快指针先遍历到第k个节点，慢指针开始遍历，当快指针遍历到尾节点时，慢指针刚好到第n-k个节点
• 原尾节点（即快指针）的next指向头节点
• 慢指针作为新的尾节点，next置空

循环链表

• 将链表的尾节点和头节点相连
• 遍历到第n-k个节点，将其作为新的尾节点，next置空

代码

/**
 * 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)return head;//边界条件：空链表
        // 统计链表节点数，k%=n
        ListNode* r=head;
        int len = 0;
        while(r!=nullptr){
            r=r->next;
            len++;
        }
        k%=len;
        // 哨兵节点
        ListNode* sentinel=new ListNode();
        sentinel->next=head;
        // 快慢指针 从头节点开始遍历，快指针p到结尾，慢指针q到第n-k个节点处
        ListNode* p=sentinel,*q=sentinel;
        int cnt=0;
        while(p->next!=nullptr){
            cnt++;
            if(cnt>k)q=q->next;
            p=p->next;
        }
        if(q->next!=nullptr){
            sentinel->next=q->next;
            // 快指针p的next指针指向头节点
            p->next=head;
            // 置空慢指针q的子节点，作为链表的尾节点
            q->next=nullptr;
        }
        return sentinel->next;
    }
};

/**
 * 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)return head;//边界条件：空链表
        // 哨兵头节点
        ListNode * sentinel = new ListNode();
        sentinel->next=head;
        // 统计链表节点数，k%=n
        ListNode* r = sentinel;
        int len = 0;
        while(r->next!=nullptr){
            r=r->next;
            len++;
        }
        // 如果k为链表结点数的倍数，即原链表不移动
        if(k%len==0)return head; 
        k%=len;
        // 连接尾节点和头节点，形成循环链表
        r->next=head;
        // 从头节点开始遍历，直到第n-k个节点
        ListNode* p=sentinel;
        int cnt=0;
        while(p->next!=nullptr){
            if(cnt==len-k)break;
            p=p->next;
            cnt++;
        }
        sentinel->next=p->next;
        // 第n-k个节点作为新的尾节点，其next指针置为空
        p->next=nullptr;
        return sentinel->next;
    }
};