题目描述

给定一个链表，将链表向右循环移动 $k$ 次，$k$ 是非负整数。

样例1

输入：1->2->3->4->5->NULL, k = 2
输出：4->5->1->2->3->NULL
解释：
向右移动1步后：5->1->2->3->4->NULL
向右移动2步后：4->5->1->2->3->NULL

样例2

输入：0->1->2->NULL, k = 4
输出：2->0->1->NULL
解释：
向右移动1步：2->0->1->NULL
向右移动2步：1->2->0->NULL
向右移动3步：0->1->2->NULL
向右移动4步：2->0->1->NULL

算法

(模拟，链表) $O(n)$

这道题中 $k$ 可能很大，所以我们令 $k = k\%n$，$n$是链表长度。

创建两个指针first, second，分别指向头结点，先让first向后移动 $k$ 个位置，然后first和second同时向后移动，直到first走到链表最后一个元素。
此时first指向链表末尾，second指向分界点。然后我们把链表从分界点处断开，然后把后半段接在前半段前面即可。

时间复杂度分析：链表一共遍历2遍，所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;

        int n = 0;
        ListNode *p = head;
        while (p)
        {
            n ++ ;
            p = p->next;
        }

        k %= n;
        if (!k) return head;


        ListNode *first = head;
        while (k -- && first) first = first->next;
        ListNode *second = head;
        while (first->next)
        {
            first = first->next;
            second = second->next;
        }
        first->next = head;
        head = second->next;
        second->next = 0;
        return head;
    }
};