感谢你一路上的陪伴

题目#

题干上让我们进行**“旋转“**操作，说是把最后的元素放到了链表头去，且下一个元素是原链表头

稍微敏感一些人都能看出来，可以发现：

或者是自己模拟一下这个过程，除了刚才被**“旋转”**的元素以外，其他的元素保持原有的顺序

这个如果是一个循环链表刚好能满足他的要求，不过是开始的起点不同

解题思路#

所以现在题目的意思就转化成了：你有一个链表，他需要是循环链表，然后你需要知道他的头是谁，最后交给系统

所以第一步就是将其变成循环链表

我们这里选择直接遍历到末尾，然后把他收尾相接

1
ListNode* head; // 假设我们有
2

3
//以下是代码
4
ListNode* tail = head;
5
while(tail->next){
6
  tail = tail->next;
7
}
8
tail->next = head;

至此，我们第一个问题就解决了

然后就是你需要知道他的头是谁，现在每进行一次**“旋转”**就会把最后的元素放到第一位去，那现在题目需要进行k次旋转，那也就是把倒数第k个元素放到头上去，然后正常遍历即可获得序列

发现问题#

那聪明的小朋友应该会发现两个问题

1. 链表怎么倒着遍历
2. 由于头尾相接了，那不就导致序列无穷无尽了

对于这两个问题解决方案分别是

1. 计算
2. 断链

有一点数学思维的同学都能知道，一般能算出来的都比模拟要来的快，那我们来算算账:

假设现在序列长为n（这个可以在刚才将链表连起来的时候加入一个变量统计），我们需要倒数第k个，那也就是正数第n-k+1个。如下图，n为5，如果k=2的时候倒数第二个是4，对于正数来说就是5-2+1=4


现在知道了头在哪了，那哪边需要断开⛓️‍💥呢，我们在来看一张图:


可以发现新的head和新的tail的关系是尾巴就是头的前一个也就是第n-k+1-1个即n-k个

由此可以得到以下操作

1
//假设已知
2
int n,k;
3
ListNode* Head;//上面已经变成循环链表了
4

5
//代码开始
6
ListNode* NewTail = Head;
7
for(int i = 1;i<n-k;i++){ //这里先找到新的尾巴,即找到n-k就跳出循环了，所以n-k不能有=
8
  NewTail = NewTail -> next;
9
}
10
ListNode* NewHead = NewTail->next;
11
NewTail -> next = nullptr;//断开⛓️‍

至此，本题结完，返回一个NewHead即可

这边要补充两个点，如果细心的同学可以发现，当这个k>n的时候实际上是轮了一圈，即k%n和k的效果是一样的，因此可以做一下取余优化

全部代码#

1
class Solution {
2
public:
3
    ListNode* rotateRight(ListNode* head, int k) {
4
        if (head == nullptr) return head;
5
        ListNode* tail = head;
6
        int n = 1;
7
        while (tail->next != nullptr) {
8
            tail = tail->next;
9
            n++;
10
        }
11
        k = k % n;
12
        tail->next = head;
13

14
        ListNode* newTail =head;
15
        for (int i = 1;i<n-k;i++) {
16
            newTail = newTail->next;
17
        }
18
        ListNode* newHead = newTail->next;
19
        newTail->next = nullptr;
20
        return newHead;
21
    }
22
};