题目内容

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示

1、链表中节点的数目在范围 [0, 500] 内
2、-100 <= Node.val <= 100
3、0 <= k <= 2 * 10^9

题解

本题考查对单链表的旋转，采用双指针的方法求解。思路如下：

首先，求出链表的长度n，当k大于链表的长度时等价于移动k = k%n位。

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

由于最坏情况，链表需要被遍历两次，因此时间复杂度近似于O(n)。

具体，请看代码。

代码

/**
 * 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) {
        int n = 0;
        if(!head) return nullptr;
        ListNode* tail;
        for(auto p = head; p; p = p->next){
            //遍历链表长度
            n++;
            tail = p;//求出尾结点
        } 
        k %= n;//将k映射为n以内的数

        if(!k) return head;//当k等于0时，链表等于不用动

        auto p = head;
        for(int i = 0; i < n - k - 1; i++) p = p->next;
        tail->next = head;
        head = p->next;
        p->next = nullptr;

        return head;
    }
};