leetcode61. 旋转链表

题目

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
（Given a linked list, rotate the list to the right by k places, where k is non-negative.）

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

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

此题一开始的想法是闭合成环，但由于不确定，因此翻看了后面牛客网的官方题解，以下是搬运牛客网的官方题解，侵删。

牛客网思路

链表中的点已经相连，一次旋转操作意味着：

1. 先将链表闭合成环
2. 找到相应的位置断开这个环，确定新的链表头和链表尾

【图片源自牛客网，侵删】

• step1：断开尾部的链接，将尾部的链接连接到头部，形成闭环。
• step2：找到新的头尾节点，可以先找到尾节点，然后通过尾结点找到头节点，因为是环，头尾节点是相连的。
• step3：确定新的头尾节点后，断开头尾链接。
• step4：尾节点指向NULL，代表后面没有其他节点了。

K的取值分为两种情况：k<n，k>=n

针对k<n：

那么新的链表头在哪里？

在n-k处（n表示有n个节点）

新的链表尾在哪里？

在n-k-1处

针对K>=n：

k 可以被写成 k = (k // n) * n + k % n 两者加和的形式，其中前面的部分不影响最终的结果，因此只需要考虑 k%n 的部分，这个值一定比 n 小。

（//地板除：只取整数部分；/：小数整数都取；%：只取余数）

代码

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //base
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        
        //step1 cicrle
        ListNode* old_head = head;
        int n = 1;
        while(old_head->next != NULL){
            n += 1;
            old_head = old_head->next;
            
        }
        cout<< n <<" ";
        old_head->next = head;

        //step2
        ListNode* new_tail = head;
        for(int i = 0; i < n - k % n - 1; i++){
            new_tail = new_tail->next;
        }
        ListNode* new_head = new_tail->next;
        new_tail->next = NULL;
        return new_head;
    }
};